Exercises

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.

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.

ᴬ 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.)

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.

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}$."

Explain why the following is not a description of a legitimate Turing machine. $M_{\text{bad }}=$ "On input $\langle p\rangle$, a polynomial over variables $x_{1}, \ldots , x_{k}$ :

1. Try all possible settings of $x_{1}, \ldots , x_{k}$ to integer values. 2. Evaluate $p$ on all of these settings. 3. If any of these settings evaluates to 0, accept; otherwise, reject."

Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet 0,1.