Section 9.4 Turing Machines
775
Output
Halts with 0 on tape
exactly when T never
halts on a
Halts with 1 on tape
exactly when T
eventually halts on a
Turing machine X
Input
(s T , a)
figure 9.23
Now we add to X’s quintuples to create a new machine Y. Machine Y modifies
X’s behavior so that whenever X halts with a 1 on its tape, Y goes to a state that
moves Y endlessly to the right so that it never halts. If X halts with a 0 on its tape,
so does Y. Figure 9.24 illustrates the behavior of Y.
Output
Halts with 0 on tape
exactly when T never
halts on a
Never halts
exactly when T
eventually halts on a
Turing machine Y
Input
(s T , a)
figure 9.24
Finally, we modify Y to get a new machine Z that acts on any input b by first
copying b (see, for example, Exercise 16) and then turning the computation over
to Y so that Y acts on (b, b). What happens if we run Z on its own description, s Z ?
This situation is shown in Figure 9.25.
Output
Halts with 0 on tape
exactly when Z never
halts on s z
Never halts
exactly when Z
eventually halts on s z
Turing machine Z
Input
s z
(s z , s z )
figure 9.25