CSC 341: April 18, 2007

From CSWiki

1 Instructor's notes for the class session
2 Study questions
- 2.1 Proposed Solutions

Instructor's notes for the class session

Self-reference

For any fixed string $w$ , it is straightforward to design a Turing machine that erases any input from its tape and then prints $w$ at the left end of its tape, or alternatively one that inputs a string $x$ and outputs some conventional encoding for the pair $(w, x)$ . The characters making up the string $w$ have to be, in effect, stored in the states and transitions of the Turing machine. This is possible because $w$ is just one finite string; if we need to switch to a different string $w'$ at some point, we'll just build a different Turing machine, with different states and transitions. A Turing machine that behaves in this way is a printer (or, if it keeps its input and outputs a pair containing it, an prepender).

The process of constructing a printer (or a prepender) for a given string $w$ can be automated. There is a Turing machine, $Q$ , that takes any string as input and outputs the conventional encoding for a printer for that string.

There is a Turing machine, $S E L F$ , that erases its input and prints a conventional encoding for itself. One constructs it in two parts, $A$ and $B$ . $B$ uses its input string in two ways. On one hand, it treats that string as the conventional encoding for a Turing machine. On the other hand, it also uses $Q$ to construct a printer for that string. The output of the $B$ machine is the conventional encoding for a Turing machine in which that printer acts as a preprocessor for the Turing machine that the string encodes. The effect is that, given a string $w$ , $B$ outputs the conventional encoding for a Turing machine that erases its input and then feeds the string $w$ into the Turing machine that $w$ encodes.

Since $B$ is a Turing machine, it can be conventionally encoded in a string. Now we're ready to describe $A$ : It's simply a printer for the string that encodes $B$ .

Finally, $S E L F$ is the Turing machine that runs $A$ and $B$ in series. The $A$ part erases the input and feeds the encoding for $B$ to $B$ . Given this encoding, $B$ outputs the encoding for a Turing machine that erases its input and then feeds the encoding for $B$ into $B$ -- in other words, $B$ outputs the encoding for $S E L F$ . So $S E L F$ erases its input and outputs its own encoding.

The handout shows how to implement essentially the same idea in the recursive-function-theory model: The function that plays the role of $B$ inputs the encoding $n$ for a singulary, partial recursive function and outputs the encoding for the composition of that function with a constant function that always returns $n$ . The function that plays the role of $A$ takes no input and outputs the encoding for $B$ . The composition of $B$ with $A$ , therefore, is a nullary function that outputs the encoding for the composition of $B$ with $A$ .

[edit]

The recursion theorem

The recursion theorem shows how this process can be generalized. It says that, if there is a Turing machine $T$ that takes a Turing-machine encoding as an extra input and performs some useful computation using that encoding as well as the normal input, then there is also a more specialized Turing machine $R$ , without the extra input, that computes, for any input, the same output that $T$ would compute if given the encoding for $R$ as its extra input.

In describing such an $R$ , once we have proved the recursion theorem, we can essentially help ourselves at any point to the encoding for the very Turing machine that we are defining, proceeding as if we had that encoding as an extra input to the algorithm. This is signalled, in subsequent proofs, by the phrase "Obtain, via the recursion theorem, own description."

The proof of the recursion theorem is a self-referential construction. This time, we need a slightly different $B$ : This one takes its input as a pair, of which the car is the encoding for a Turing machine and the cdr is an arbitrary input string. $B$ selects the car and feeds it to a variant of $Q$ ; this variant $Q$ outputs the encoding for a prepender that attaches its input to the string that $Q$ receives. $B$ then calculates and outputs the encoding for a Turing machine that feeds the output from that prepender into the Turing machine described by the input to $B$ . Finally, $B$ recovers the cdr of the pair that it received as input, conses it to the composite encoding that it has constructed, and outputs the result.

Now that we have both $B$ and $T$ , we can construct a Turing machine that runs them in series, with the output from $B$ being passed as the input to $T$ . The resulting machine has an encoding. $A$ is a prepender for this encoding.

Our overall machine $R$ , then, runs $A$ , $B$ , and $T$ in series. $A$ runs first, prepending an encoding for the composite $B T$ machine to the input to $R$ . Then $B$ extracts the encoding for $B T$ , runs it through variant $Q$ to get $A,$ calculates the encoding for the composite machine $A B T$ (which is $R$ ), conses together that encoding and the original input to $R$ , and passes the result to $T$ , which outputs the final value, using both the encoding for $R$ and the original input to $R$ as data.

The handout shows the corresponding construction in the recursive-function-theory model. In one way, it's simpler, because we can pass the input to $R$ through to $T$ without the laborious pairing and unpairing; in another way, it's more complicated, because we have to manage all the details of getting valences right. But the idea is straightforward.

[edit]

Applications

Sipser proceeds to show, first, how the use of the recursion theorem can simplify the proof of the undecidability of $A_\texttt{TM}$ ; it becomes almost trivial.

Second, Sipser proves that the set of minimal Turing-machine encodings is not Turing-recognizable, in a way that seems almost magical. It's a proof by contradiction.

Suppose that that set is Turing-recognizable. Then there is an enumerator for it. We can therefore build a Turing machine that first (via the recursion theorem) obtains its own encoding and measures its length, then runs the enumerator until the enumerator prints a longer encoding. Then we use our universal Turing machine $U$ to simulate the machine encoded by that "longer encoding" on the input to the machine we're building, accepting if the simulation accepts and rejecting if it rejects.

This machine recognizes the same language as the one encoded by the "longer encoding", so the "longer encoding" isn't minimal. But the enumerator printed it, so it must be minimal. That's the contradiction.

Third, Sipser uses the recursion theorem in the proof of the fixed-point theorem, which says that, for any computable function $t$ , there is a Turing machine $F$ such that, given the encoding for $F$ as input, $t$ outputs the encoding for a Turing machine that is equivalent to (that is, accepts the same language as) $F$ . (For this to work in absolutely every case, every string must be counted as the encoding for a Turing machine; strings that we have previously regarded as not encoding any Turing machine will, for the purpose of this theorem, be regarded as encoding a Turing machine that rejects every input.)

The proof is easy: The $F$ obtains its own encoding, computes the result of applying $t$ to it, and uses the universal Turing machine $U$ to simulate the operation of the Turing machine that $t(\langle F\rangle)$ encodes on the input $F$ receives, accepting if the simulation accepts and rejecting if it rejects. $F$ accepts the same language as the machine encoded by $t(\langle F\rangle)$ , since it simulates that machine in order to obtain its answer.

[edit]

Study questions

Prove that there is a Turing machine $M$ such that $L(M) = \{\langle M \rangle\}$ . (In other words, the only string that $M$ accepts is its own encoding.)
Prove that there are Turing machines $M 0$ and $M 1$ such that $L(M_0) = \{\langle M_1 \rangle\}$ and $L(M_1) = \{\langle M_0 \rangle\}$ .
In your favorite programming language, write analogues of the Turing machine $Q$ (a printer generator), the variant of $Q$ that generates prependers, and $S E L F$ .