\documentclass{article}

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

\begin{document}

\homework{6}{Nancy Lynch}{Due: March 19, 2007}{Elena Grigorescu}

\begin{problem} 
Prove that the following languages are undecidable.
Use reductions from $A_{TM}$ or other problems already known to be
undecidable.
Here, $\Sigma = \{ 0, 1 \}$.
\begin{enumerate}
\item
$L_1 = \{ <M> : M \mbox{ is a Turing machine and } M \mbox{
accepts the empty string } \epsilon \}$.
\item
$L_2 = \{ <M> : M \mbox{ is a Turing machine and } L(M) \mbox{ is
  infinite } \}$.
\end{enumerate}
\end{problem}

\begin{problem} 
(From Sipser problems 4.19 and 5.9)
\begin{enumerate}
\item
Let $S = \{ <M> | M \mbox{ is a DFA that accepts } w^R \mbox{ whenever
  it accepts } w \}$.  Prove that $S$ is decidable.
\item
Let $T = \{ <M> | M \mbox{ is a basic Turing machine that accepts }
w^R \mbox{ whenever it accepts } w \}$.  Prove that $T$ is undecidable.
\end{enumerate}
\end{problem}

\begin{problem} 
(From Sipser, problem 4.28) \\
Let $A=\{<D_1>,<D_2>,<D_3>,\dots\}$ be an infinite language consisting
of representations of Turing machines that are deciders, that is, each
machine $D_i$ halts (accepts or rejects) on every input.  Suppose that
$A$ is Turing-recognizable, and therefore, enumerable by an enumerator
machine $E$.

Show that there must be some decidable language that is not
decided by any of the machines represented in $A$ (i.e., some language
$L(D')$ that is decided by a machine $D'$ such that $<D'> \not\in
A$). 

Note that this time, countability arguments are not going to help:
there are only countably many machine descriptions in $A$, but then again,
there are also only countably many decidable languages.  Still, $A$
cannot contain descriptions of deciders for {\em all} decidable languages.

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


\begin{problem}
Consider the machine $M_2$ on page 143 of Sipser's book, which
recognizes the language consisting of all strings of $0$s whose length
is a power of $2$.
\begin{enumerate}
\item
Write out the accepting computation history for the machine $M_2$ on
input $00$.
\item
What are the dominoes for the instance of the Post Correspondence
Problem defined for $M_2$ and input $00$?
\item
Write out your computation history from part (a) twice, one copy above
the other.
Draw lines indicating how your dominoes from part (b) can be used to
establish a correspondence between these two copies.
\end{enumerate}
\end{problem}

\end{document}





