764
Modeling Arithmetic, Computation, and Languages
Since there are no quintuples defining the action to be taken when in state 1 reading
b, the machine halts with final tape:
b 1
...
0 0 0 0 b ...
The tape serves as a memory medium for a Turing machine, and in general,
the machine can reread cells of the tape. Since it can also write on the tape, the
nonblank portion of the tape can be as long as desired, although there are still only
a finite number of nonblank cells at any time. Hence the machine has available an
unbounded, though finite, amount of storage. Because Turing machines overcome
the limitations of finite-state machines, Turing machines should have considerably higher capabilities. In fact, a finite-state machine is a very special case of a
Turing machine, one that always prints the old symbol on the cell read, always
moves to the right, and always halts on the symbol b.
PrACtiCe 57 Consider the following Turing machine:
(0, 0, 0, 1, R)
(0, 1, 0, 0, R)
(0, b, b, 0, R)
(1, 0, 1, 0, R)
(1, 1, 1, 0, L)
a. What is the final tape, given the initial tape
b 1
...
0 b ...
(Since it is tedious to draw all the little squares, you don’t need to do so; just write down the contents
of the final tape.)
b. Describe the behavior of the machine when started on the tape
b
1
...
0
b ...
c. Describe the behavior of the machine when started on the tape
b
...
0 0 b ...
■
Parts (b) and (c) of Practice 57 illustrate two ways in which a Turing machine can
fail to halt: by endlessly cycling or by moving forever along the tape.
turing Machines as set recognizers
Although the Turing machine computations we have seen so far are not particularly
meaningful, we will use the Turing machine to do two kinds of jobs. First, we’ll
Modeling Arithmetic, Computation, and Languages
Since there are no quintuples defining the action to be taken when in state 1 reading
b, the machine halts with final tape:
b 1
...
0 0 0 0 b ...
The tape serves as a memory medium for a Turing machine, and in general,
the machine can reread cells of the tape. Since it can also write on the tape, the
nonblank portion of the tape can be as long as desired, although there are still only
a finite number of nonblank cells at any time. Hence the machine has available an
unbounded, though finite, amount of storage. Because Turing machines overcome
the limitations of finite-state machines, Turing machines should have considerably higher capabilities. In fact, a finite-state machine is a very special case of a
Turing machine, one that always prints the old symbol on the cell read, always
moves to the right, and always halts on the symbol b.
PrACtiCe 57 Consider the following Turing machine:
(0, 0, 0, 1, R)
(0, 1, 0, 0, R)
(0, b, b, 0, R)
(1, 0, 1, 0, R)
(1, 1, 1, 0, L)
a. What is the final tape, given the initial tape
b 1
...
0 b ...
(Since it is tedious to draw all the little squares, you don’t need to do so; just write down the contents
of the final tape.)
b. Describe the behavior of the machine when started on the tape
b
1
...
0
b ...
c. Describe the behavior of the machine when started on the tape
b
...
0 0 b ...
■
Parts (b) and (c) of Practice 57 illustrate two ways in which a Turing machine can
fail to halt: by endlessly cycling or by moving forever along the tape.
turing Machines as set recognizers
Although the Turing machine computations we have seen so far are not particularly
meaningful, we will use the Turing machine to do two kinds of jobs. First, we’ll