move left one cell, then halt in final state q 1 .
Figure 9.3 shows several stages of the process for a simple initial
configuration.
Figure 9.3
A sequence of moves.
As before, we can use transition graphs to represent Turing machines. Now
we label the edges of the graph with three items: the current tape symbol, the
symbol that replaces it, and the direction in which the read-write head is to
move. The Turing machine in Example 9.2 is represented by the transition graph
in Figure 9.4.
Figure 9.4
Example 9.3
Look at the Turing machine in Figure 9.5. To see what will happen, we can trace
a typical case. Suppose that the tape initially contains ab…, with the read-write
head on the a. The machine then reads the a, but does not change it. Its next state
is q 1 and the read-write head moves right, so that it is now over the b. This
symbol is also read and left unchanged. The machine goes back into state q 0 and
the read-write head moves left. We are now back exactly in the original state,
and the sequence of moves starts again. It is clear from this that the machine,
whatever the initial information on its tape, will run forever, with the read-write