head moving alternately right then left, but making no modifications to the tape.
This is an instance of a Turing machine that does not halt. In analogy with
programming terminology, we say that the Turing machine is in an infinite loop.
Figure 9.5
Since one can make several different definitions of a Turing machine, it is
worthwhile to summarize the main features of our model, which we will call a
standard Turing machine:
1. The Turing machine has a tape that is unbounded in both directions,
allowing any number of left and right moves.
2. The Turing machine is deterministic in the sense that δ defines at most one
move for each configuration.
3. There is no special input file. We assume that at the initial time the tape has
some specified content. Some of this may be considered input. Similarly,
there is no special output device. Whenever the machine halts, some or all
of the contents of the tape may be viewed as output.
These conventions were chosen primarily for the convenience of subsequent
discussion. In Chapter 10, we will look at other versions of Turing machines and
discuss their relation to our standard model.
Here, as in the case of pda's, the most convenient way to exhibit a sequence
of configurations of a Turing machine uses the idea of an instantaneous
description. Any configuration is completely determined by the current state of
the control unit, the contents of the tape, and the position of the read-write head.
We will use the notation in which
x 1 qx 2