The Church-Turing Thesis

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.

Let a $k$-PDA be a pushdown automaton that has $k$ stacks. Thus a 0-PDA is an NFA and a 1-PDA is a conventional PDA. You already know that 1-PDAs are more powerful (recognize a larger class of languages) than 0-PDAs.

ᴬ Say that a 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.)

A 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.

A Turing machine with left reset is similar to an ordinary Turing machine, but the transition function has the form

If $\delta (q, a)=(r, b$, 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.

A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form

At each point, the machine can move its head right or let it stay in the same position. Show that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?

A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end and read only at the right-hand end. Each write operation (we'll call it a push) adds a symbol to the left-hand end of the queue and each read operation (we'll call it a pull) reads and removes a symbol at the right-hand end. As with a PDA, the input is placed on a separate read-only input tape, and the head on the input tape can move only from left to right. The input tape contains a cell with a blank symbol following the input, so that the end of the input can be detected. A queue automaton accepts its input by entering a special accept state at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turing-recognizable.

Show that the collection of decidable languages is closed under the operation of

Show that the collection of Turing-recognizable languages is closed under the operation of

• Let $B=\left\{ \left\langle M_{1}\right\rangle ,\left\langle M_{2}\right\rangle , \ldots \right\}$ be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language $C$ consisting of TM descriptions such that every machine described in $B$ has an equivalent machine in $C$ and vice versa.

• Show that a language is decidable iff some enumerator enumerates the language in the standard string order.

• Show that every infinite Turing-recognizable language has an infinite decidable subset.

• Show that single-tape TMs that cannot write on the portion of the tape containing the input string recognize only regular languages.

Let $c_{1} x^{n}+c_{2} x^{n-1}+\cdots +c_{n} x+c_{n+1}$ be a polynomial with a root at $x=x_{0}$. Let $c_{\text{max }}$ be the largest absolute value of a $c_{i}$. Show that

ᴬ Let $A$ be the language containing only the single string $s$, where

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.