Homework 1

This homework covers the material from lectures 1 to 4.

Due date: September 20th, 10pm Waterloo time.

Required Exercises

Problem 1 - Implementing Turing Machines (30 points)

Part 1 (20 points)

Implement deterministic, one-tape Turing machines that decide the following languages. More precisely, we want you to give us the complete description of your Turing machine (i.e., the $3$-tuple $(S, \Gamma, \tau)$) and the high-level description of how your Turing machine works.

1. $L_1 = \{w \in \{0, 1\}^* \mid w \text{ is a palindrome}\}$
2. $L_2 = \{w \in \{0, 1\}^* \mid w \text{ has an equal number of 0s and 1s}\}$

Part 2 (10 points)

For each of the Turing machines you implemented in Part 1, provide the computation history for the inputs $w = 010$ and $w = 0110$.

Problem 2 - Recognizability (10 points)

Let $L = \{ w \mid w = 0x \text{ for some } x \in A_{TM} \text{ or } w = 1y \text{ for some } y \in \overline{A_{TM}} \}$. Show that neither $L$ nor $\overline{L}$ is Turing-recognizable.

Problem 3 - Decidability (20 points)

Let $L = \{ \langle M \rangle \mid M \text{ is a Turing machine that accepts } w^R \text{ whenever it accepts } w \}$, where $w^R$ is the reverse of $w$. Show that $L$ is undecidable.

Problem 4 - Decidability (20 points)

A useless state in a Turing machine is a state that is never entered during the computation of the machine on any input. Let $L = \{ \langle M \rangle \mid M \text{ is a Turing machine that has a useless state} \}$. Show that $L$ is undecidable.

Problem 5 - Recursion Theorem and Fixed Points (20 points)

A fixed point of a function $f$ is a value $x$ such that $f(x) = x$.

Use the recursion theorem to prove the following “fixed-point theorem”:

Let $t : \Sigma^* \rightarrow \Sigma^*$ be a computable function. Then there exists a Turing machine $M$ such that $t(\langle M \rangle)$ describes a Turing machine equivalent to $M$.

In the above theorem, $t$ is the function and $\langle M \rangle$ is a fixed point of $t$.