Chapter 3: Chapter 3

Let \(A\) be the language containing only the single string \(s\), where $$ s= \begin{cases}0 & \text { if life never will be found on Mars. } \\ 1 & \text { if life will be found on Mars someday. }\end{cases} $$ 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.

(a) For any two decidable languages \(L_{1}\) and \(L_{2}\), let \(M_{1}\) and \(M_{2}\) be the TMs that decide them. We construct a $\operatorname{TM} M^{\prime}\( that decides the union of \)L_{1}\( and \)L_{2}$ : "On input w: 1\. Run \(M_{1}\) on \(w\). If it accepts, accept. 2\. Run \(M_{2}\) on \(w\). If it accepts, accept. Otherwise, reject." \(M^{\prime}\) accepts \(w\) if either \(M_{1}\) or \(M_{2}\) accepts it. If both reject, \(M^{\prime}\) rejects.

(a) For any two Turing-recognizable languages \(L_{1}\) and \(L_{2}\), let \(M_{1}\) and \(M_{2}\) be the TMs that recognize them. We construct a TM \(M^{\prime}\) that recognizes the union of \(L_{1}\) and \(L_{2}\) : "On input w: 1\. Run \(M_{1}\) and \(M_{2}\) alternately on \(w\) step by step. If either accepts, accept. If both halt and reject, reject." If either \(M_{1}\) or \(M_{2}\) accepts \(w, M^{\prime}\) accepts \(w\) because the accepting TM arrives to its accepting state after a finite number of steps. Note that if both \(M_{1}\) and \(M_{2}\) reject and either of them does so by looping, then \(M^{\prime}\) will loop.

The language \(A\) is one of the two languages \(\\{0\\}\) or \(\\{1\\} .\) In either case, the language is finite and hence decidable. If you aren't able to determine which of these two languages is \(A\), you won't be able to describe the decider for \(A\). However, you can give two Turing machines, one of which is \(A\) 's decider.

Give a formal definition of an enumerator. Consider it to be a type of two- tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language.

Examine the formal definition of a Turing machine to answer the following questions, and explain your reasoning. a. Can a Turing machine ever write the blank symbol \(\lrcorner\) on its tape? b. Can the tape alphabet \(\Gamma\) be the same as the input alphabet \(\Sigma\) ? c. Can a Turing machine's head ever be in the same location in two successive steps? d. Can a Turing machine contain just a single state?

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}, \ldots\) is a list of all strings in \(\Sigma^{*}\). \(E={ }^{*}\) Ignore the input. 1\. Repeat the following for \(i=1,2,3, \ldots\) 2\. Run \(M\) on \(s_{i}\). 3\. If it accepts, print out \(s_{i} . "\)

Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet \(\\{0,1\\}\). A a. \(\\{w \mid w\) contains an equal number of 0 and 1 s \(\\}\) b. \(\\{w \mid w\) contains twice as many 0 s as 1 s \(\\}\) c. \(\\{w \mid w\) does not contain twice as many \(0 \mathrm{~s}\) as $1 \mathrm{~s}\\}$