Section 9.4 Turing Machines
761
A Turing machine consists of a finite-state machine and an unlimited tape
divided into cells, each cell containing at most one symbol from an allowable
finite alphabet. At any one instant, only a finite number of cells on the tape are
nonblank. We use the special symbol b to denote a blank cell. The finite-state
unit, through its read–write head, reads one cell of the tape at any given moment
(Figure 9.15).
b
...
...
b b b b
1 1 0 0 1
↑
Finite-state unit
figure 9.15
By the next clock pulse, depending on the present state of the unit and the
symbol read, the unit either does nothing (halts) or completes three actions:
1. Print a symbol from the alphabet on the cell read (it might be the same
symbol that’s already there).
2. Go to the next state (it might be the same state as before).
3. Move the read–write head one cell left or right.
We can describe the actions of any particular Turing machine by a set of
quintuples of the form (s, i, i′, s′, d), where s and i indicate the present state
and the tape symbol being read, i′ denotes the symbol printed, s′ denotes the
new state, and d denotes the direction in which the read–write head moves
(R for right, L for left).
Thus, a machine in the configuration illustrated by Figure 9.16a, if acting according to the instructions contained in the quintuple (2, 1, 0, 1, R), would move to
b
...
...
...
...
0 1 b b
b 1 1 0 1
b
(a)
b
0 1 b b
b 1 1 0 0
b
(b)
↑
2
↑
1
figure 9.16
(s,
i,
i′,
s′,
d)
Present state Present symbol Symbol printed Next state Direction of move
761
A Turing machine consists of a finite-state machine and an unlimited tape
divided into cells, each cell containing at most one symbol from an allowable
finite alphabet. At any one instant, only a finite number of cells on the tape are
nonblank. We use the special symbol b to denote a blank cell. The finite-state
unit, through its read–write head, reads one cell of the tape at any given moment
(Figure 9.15).
b
...
...
b b b b
1 1 0 0 1
↑
Finite-state unit
figure 9.15
By the next clock pulse, depending on the present state of the unit and the
symbol read, the unit either does nothing (halts) or completes three actions:
1. Print a symbol from the alphabet on the cell read (it might be the same
symbol that’s already there).
2. Go to the next state (it might be the same state as before).
3. Move the read–write head one cell left or right.
We can describe the actions of any particular Turing machine by a set of
quintuples of the form (s, i, i′, s′, d), where s and i indicate the present state
and the tape symbol being read, i′ denotes the symbol printed, s′ denotes the
new state, and d denotes the direction in which the read–write head moves
(R for right, L for left).
Thus, a machine in the configuration illustrated by Figure 9.16a, if acting according to the instructions contained in the quintuple (2, 1, 0, 1, R), would move to
b
...
...
...
...
0 1 b b
b 1 1 0 1
b
(a)
b
0 1 b b
b 1 1 0 0
b
(b)
↑
2
↑
1
figure 9.16
(s,
i,
i′,
s′,
d)
Present state Present symbol Symbol printed Next state Direction of move