chapter3.tex

\section{Chapter 3}
\begin{enumerate}

\newcommand{\bl}{{\sqcup}}

%		3.1		%
\item[3.1]This exercise concerns TM $M_2$, whose description and state diagram appear in Example 3.7. In each of the parts, give the sequence of configurations that $M_2$ enters when started on the indicated input string.
\begin{enumerate}
\item[a.]0. \textbf{Solution:} $q_{1}0 \to \bl q_2\bl \to{\bl}{\bl}q_{accept}$.
\item[b.]00. \textbf{Solution:} \alreadyanswered
\item[c.]000. \textbf{Solution:} $q_{1}000 \to \bl q_2 00 \to \bl x q_3 0 \to \bl x 0 q_4 \bl \to \bl x 0{\bl}q_{reject}$.
\item[d.]000000. \textbf{Solution:} $q_{1}000000 \to \bl q_2 00000 \to \bl x q_3 0000 \bl \to \bl x 0 q_4 000 \to \bl x 0 x q_3 00 \to \bl x 0 x 0 q_4 0 \to \bl x0x0xq_3 \bl \to \bl x0x0q_5x\bl \to \bl x0xq_5 0x\bl \to \bl x 0 q_5 x 0 x \bl \to \bl x q_5 0x0x\bl \to \bl q_5 x0x0x\bl \to q_5{\bl}x0x0x\bl \to \bl q_2 x0x0x \bl \to \bl x q_2 0x0x\bl \to \bl xxq_3 x0x\bl \to \bl xxxq_3 0 x\bl \to \bl xxx0q_4 x \bl \to \bl xxx0xq_4 \bl \to \bl xxx0x{\bl}q_{reject}$. 
\end{enumerate}

%		3.2		%
\item[3.2]This exercise concerns TM $M_1$, whose description and state diagram appear in Example 3.9. In each of the parts, give the sequence of configurations that $M_1$ enters when started on the indicated input string.
\begin{enumerate}
\item[a.]11. \textbf{Solution:} \alreadyanswered
\item[b.]1\#1. \textbf{Solution:} $q_1 1\#1 \to xq_3 \# 1 \to x\# q_5 1 \to xq_6 \#x \to q_7 x \# x \to xq_1 \# x \to x\#q_8 x \to x\#q_8\bl \to x\#x{\bl}q_{accept} \bl$.
\item[c.]1\#\#1. \textbf{Solution:} $q_1 1\#\#1 \to xq_3 \#\#1 \to x\#q_5\#1 \to x\#\#q_{reject}1$.
\item[d.]10\#11. \textbf{Solution:} $q_1 10\#11 \to xq_30\#11 \to x0q_3\#11 \to x0\#q_511 \to x0q_6\#x1 \to xq_7 0 \#x1 \to q_7 x 0\#x1 \to xq_1 0 \#x1 \to xxq_2\#x1 \to xx\#q_4 x1 \to xx\#xq_4 1\to xx\#x1q_{reject}\bl$.
\item[e.]10\#10. \textbf{Solution:} $q_1 10\#10 \to xq_30\#10 \to x0q_3\#10 \to x0\#q_510 \to x0q_6\#x0 \to xq_70\#x0 \to q_7x0\#x0 \to xq_10\#x0 \to xxq_2\#x0 \to xx\#q_4x0 \to xx\#xq_40 \to xx\#q_6xx \to xxq_6\#xx \to xq_7x\#xx \to xq_7x\#xx \to xxq_1\#xx \to xx\#q_8 xx \to xx\#xq_8 x \to xx\#xxq_8\bl \to xx\#xx\bl q_{accept} \bl$.
\end{enumerate}

%		3.3		%
\item[3.3]Modify the proof of Theorem 3.16 to obtain Corollary 3.19, showing that a language is decidable iff some nondeterministic Turing machine decides it. (You may assume the following theorem about trees. If every node in a tree has finitely many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.)
\\
\textbf{Solution:} \alreadyanswered

%		3.5		%
\item[3.5]Examine the formal definition of a Turing machine to answer the following questions, and explain your reasoning.
\\
\textbf{Solution:} \alreadyanswered

%		3.6		%
\item[3.6]In Theorem 3.21, we showed that a language is Turing-recognizable iff some enumerator enumerates it. Why didn?t we use the following simpler algorithm for the forward direction of the proof? As before, $s_1, s_2, \cdots$ is a list of all strings in $\Sigma^*$.
\\
$E$ = ``Ignore the input.
\begin{enumerate}
\item Repeat the following for $i=1,2,3,\cdots$.
\item Run $M$ on $s_i$.
\item If it accepts, print out si."
\end{enumerate}
\textbf{Solution:} The second step might run forever, and therefore $E$ may not move onto the next string.  

%		3.7		%
\item[3.7]Explain why the following is not a description of a legitimate Turing machine.
\\
$M_{bad}$ = ``On input $\langle p \rangle$, a polynomial over variables $x_1, \cdots, x_k$:
\begin{enumerate}
\item Try all possible settings of $x_1, \cdots, x_k$ to integer values.
\item Evaluate $p$ on all of these settings.
\item If any of these settings evaluates to 0, \emph{accept}; otherwise, \emph{reject}."
\end{enumerate}
\textbf{Solution:} it's not a valid description because the machine will never halt, and the first step alone will take infinite time. 

%		3.10		%
\item[3.10]Say that a \textbf{\emph{write-once Turing machine}} is a single-tape TM that can alter each tape square at most once (including the input portion of the tape). Show that this variant Turing machine model is equivalent to the ordinary Turing machine model. (Hint: As a first step, consider the case whereby the Turing machine may alter each tape square at most twice. Use lots of tape.)
\\
\textbf{Solution:} \alreadyanswered

%		3.11		%
\item[3.11] A \emph{\textbf{Turing machine with doubly infinite tape}} is similar to an ordinary Turing machine, but its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion that contains the input. Computation is defined as usual except that the head never encounters an end to the tape as it moves leftward. Show that this type of Turing machine recognizes the class of Turing-recognizable languages.
\\
\textbf{Solution:} we simulate a doubly-infinite TM with an ordinary one with 2 tapes (which is equivalent to single-tape TMs). The first tape starts with the input string, and the second is blank. Cut the doubly-infinite tape into 2 parts, at the start of the input string, and these two parts are the same as the two tapes.

%		3.12		%
\item[3.12]A \textbf{\emph{Turing machine with left reset}} is similar to an ordinary Turing machine, but the transition function has the form
\[
\delta \colon Q \times \Gamma \rightarrow Q \times \Gamma \times \{\text{R, RESET}\}
\]
If $\delta(q, a) = (r, b, \text{RESET})$, when the machine is in state $q$ reading an $a$, the machine?s head jumps to the left-hand end of the tape after it writes $b$ on the tape and enters state $r$. Note that these machines do not have the usual ability to move the head one symbol left. Show that Turing machines with left reset recognize the class of Turing-recognizable languages.
\\
\textbf{Solution:} Let $M$ be a TM. We will construct a TM with left-reset $L$ as follows: \\
$L$ = ``On input w:
\begin{enumerate}
\item If $q$ is a halting (i.e., accept or reject) state, go to step d. Otherwise, execute Steps b or c depending on whether the current transition is right or left.
\item If the current transition is right:
\begin{enumerate}
\item For the current tape symbol $s$, and for $\delta(q, a) = (q', b, R)$, replace the $a$ with a $b$ and then RESET.
\item Scan right for a marked symbol - if there are none, RESET and mark the first symbol. Then, move the head to the right, change $L$'s state to $q'$, and go back to step a. If there is a marked symbol, move the tape head right.
\item Mark the symbol under the tape head, move right, and change $L$'s state to be $q'$. Then, go back to step a. 
\end{enumerate}
\item If the current transition is left:
\begin{enumerate}
\item If $\delta(q, a) = (q', b, L)$, replace the $a$ with $b$ and then RESET.
\item If the first symbol is marked, remove the mark, and then RESET. Also, change $L$'s state to be $q'$ and go back to step a. 
\item Scan right for a marked symbol - if there are none, \emph{reject} $w$. Otherwise, if one is found, RESET and mark the first symbol.
\item If the next symbol is marked, unmark it and RESET. Also, move right and change $L$'s state to be $q'$, and go back to step a.
\item If the second symbol is not marked:
\begin{enumerate}
\item RESET, move right to the first marked cell, and unmark it and move right again.
\item Mark the current tape cell and move right again.
\item If the current tape cell is unmarked, go back to A. Otherwise, unmark it and RESET.
\item Move right to the first marked cell. Move right and change $L$'s state to $q'$ and go back to step a.
\end{enumerate}
\end{enumerate}
\item If $q'$ is an accept state, then \emph{accept} $w$; otherwise, \emph{reject} $w$."
\end{enumerate}

%		3.15		%
\item[3.15]Show that the collection of decidable languages is closed under the operation of
\begin{enumerate}
\item[a.]union. \textbf{Solution:} \alreadyanswered
\end{enumerate}

%		3.16		%
\item[3.16]Show that the collection of Turing-recognizable languages is closed under the operation of
\begin{enumerate}
\item[a.]union. \textbf{Solution:} \alreadyanswered
\end{enumerate}

%		3.18		%
\item[3.18]Show that a language is decidable iff some enumerator enumerates the language in the standard string order.
\\
\textbf{Solution:} let the language be $L$. If $L$ is decidable, then we can just generate strings in lexicographic order, and test if each is in $L$, thus generating an enumerator that prints in standard string order. If we have such an enumerator $E$:
\begin{enumerate}
\item If $L$ is finite, then just hardwire each of the strings in $L$ in $E$.
\item If $L$ is infinite, then on an input $w$, run $E$ to print all strings in standard string order until a string lexicographically after $w$ appears; if $w$ has appeared, accept; otherwise, reject.
\end{enumerate}

%		3.22		%
\item[3.22]Let $A$ be the language containing only the single string $s$, where $s = 0$ if life never will be found on Mars, and $s = 1$ if life will be found on Mars someday. Is $A$ decidable? Why or why not? For the purposes of this problem, assume that the question of whether life will be found on Mars has an unambiguous YES or NO answer.
\\
\textbf{Solution:} \alreadyanswered

\end{enumerate}