\documentclass{article}

\input{6045preamble}
\usepackage{amssymb,amsmath,graphicx}

\begin{document}

\homework{5}{Nancy Lynch}{Due: March 16, 2005}{Vinod Vaikuntanathan}

\noindent
\begin{problem} 
Prove that the following languages are undecidable.
Use reductions from $A_{TM}$ or other problems already known to be
undecidable.
In all these problems, $\Sigma = \{ 0, 1 \}$.
\begin{enumerate}
\item
$L_1 = \{ <M> : M \mbox{ is a Turing machine and } M 
\mbox{ accepts the string } 001 \}$.
\item
$L_2 = \{ <M> : M \mbox{ is a Turing machine,} M \mbox{ accepts }
001 \mbox{ and } M \mbox{ does not accept } 110 \}$.
\item
$L_3 = \{ <M> : M \mbox{ is a Turing machine and } M \mbox{
accepts exactly the strings that are palindromes} \}$.
\end{enumerate}
\end{problem}

\noindent
\begin{problem} 
Let $A=\{<D_1>,<D_2>,<D_3>,\dots\}$ be a language consisting of
string representations of Turing machines that are deciders, that is,
each machine $D_i$ halts (accepts or rejects) on every input.  
{\em The goal of this problem 
is to prove that $A$ is not Turing-recognizable.}

Suppose, for contradiction, 
that $A$ is Turing-recognizable, and therefore, enumerable by
an enumerator machine $E$.
Show that $A$ cannot include deciders for all decidable
languages---some decidable language must be left out.
That is, there is some decidable language $L$ that is not equal to
$L(D_i)$ for any $i$.

(Hint: Recall the diagonalization method; try constructing $L$ using
the enumerator $E$.)
\end{problem}

\noindent
\begin{problem} 
Find a match in the following instance of the PCP: \\
$$\left\{\genfrac{\lbrack}{\rbrack}{}{}{ab}{abab},
\genfrac{\lbrack}{\rbrack}{}{}{b}{a},
\genfrac{\lbrack}{\rbrack}{}{}{aba}{b},
\genfrac{\lbrack}{\rbrack}{}{}{aa}{a}\right\}$$
\end{problem}

\noindent
\begin{problem}
Consider the machine $M_1$ on page 132 of (the old edition of) 
Sipser's book, which
recognizes the language consisting of all strings of the form $w \# w$,
where $w \in \{ 0, 1\}^*$.
\begin{enumerate}
\item
Write out the accepting computation history for the machine $M_2$ on
input $0\#0$.
\item
What are the tiles for the instance of the Modified Post
Correspondence Problem defined for $M_1$ and input $0\#0$?
What is the initial tile?
\item
Write out your computation history from part (a) twice, one copy above
the other.
Draw lines indicating how your tiles from part (b) can be used to
match these two copies.
\end{enumerate}
\end{problem}

\end{document}