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,\mathrm{\Gamma },\tau )$) and the high-level description of how your Turing machine works.

1. $L_1=\{w\in \{0,1{\}}^{\ast }\mid w\text{ is a palindrome}\}$
2. $L_2=\{w\in \{0,1{\}}^{\ast }\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 $\bar{L}$ is Turing-recognizable.

Problem 3 - Decidability (20 points)

Let $L=\{⟨M⟩\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=\{⟨M⟩\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:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Sigma }}^{\ast }$ be a computable function. Then there exists a Turing machine $M$ such that $t(⟨M⟩)$ describes a Turing machine equivalent to $M$.

In the above theorem, $t$ is the function and $⟨M⟩$ is a fixed point of $t$.