Section 9.4 Turing Machines
765
use it as a recognizer, much as we considered finite-state machines as recognizers
in the previous section. We can even give a very similar definition, provided we
first define a final state for a Turing machine. A final state in a Turing machine
is one that is not the first symbol in any quintuple. Thus, on entering a final state,
whatever the symbol read, the Turing machine halts.
Definition turinG MAChinE rECoGnition (ACCEPtAnCE)
A Turing machine T with tape alphabet I recognizes (accepts) a subset S of I* if
T, beginning in standard initial configuration on a tape containing a string α of
tape symbols, halts in a final state if and only a [ S.
Note that our definition of acceptance leaves open two possible behaviors for T
when applied to a string a of tape symbols not in S. T may halt in a nonfinal state,
or T may fail to halt at all.
We can now build a Turing machine to recognize our old friend
S = 50
n
1
n
0 n ≥ 06. The machine is based on our second approach to this recognition problem, sweeping back and forth across the input and crossing out
0–1 pairs.
example 41
We want to build a Turing machine that will recognize S = 50
n
1
n
0 n ≥ 06. We will
use one additional special symbol, call it X, to mark out (“erase”) the 0s and 1s
already examined. Thus the tape alphabet is I = 50, 1, b, X6. State 6 is the only
final state. The quintuples making up T are given below. Each quintuple or group
of quintuples has a “comment” describing its function. Just like well-written comments in computer code, this makes the Turing instructions much easier to understand. Be sure to include comments in any Turing machine definition.
(0, b, b, 6, R)
Recognizes the empty tape, which is in S.
(0, 0, X, 1, R)
Erases the leftmost 0 and begins to move right.
(1, 0, 0, 1, R)
(1, 1, 1, 1, R)
(1, b, b, 2, L)
(1, X, X, 2, L)
(2, 1, X, 3, L)
Erases the rightmost 1 and begins to move left.
(3, 1, 1, 3, L)
Moves left over 1s.
(3, 0, 0, 4, L)
Goes to state 4 if more 0s are left.
(3, X, X, 5, R)
Goes to state 5 if no more 0s in string.
(4, 0, 0, 4, L)
Moves left over 0s.
(4, X, X, 0, R)
Finds left end of binary string and begins sweep again.
(5, X, X, 6, R)
No more 1s in string; machine accepts.
Reading down the columns in Figure 9.18, we can see the key configurations (skipping some routine steps) in the machine’s behavior on the tape
b
...
0 0 0 1 1 1 b ...
which, of course, it should accept.
∂
Moves right in state 1 until it reaches the end of the binary
string; then moves left in state 2.
765
use it as a recognizer, much as we considered finite-state machines as recognizers
in the previous section. We can even give a very similar definition, provided we
first define a final state for a Turing machine. A final state in a Turing machine
is one that is not the first symbol in any quintuple. Thus, on entering a final state,
whatever the symbol read, the Turing machine halts.
Definition turinG MAChinE rECoGnition (ACCEPtAnCE)
A Turing machine T with tape alphabet I recognizes (accepts) a subset S of I* if
T, beginning in standard initial configuration on a tape containing a string α of
tape symbols, halts in a final state if and only a [ S.
Note that our definition of acceptance leaves open two possible behaviors for T
when applied to a string a of tape symbols not in S. T may halt in a nonfinal state,
or T may fail to halt at all.
We can now build a Turing machine to recognize our old friend
S = 50
n
1
n
0 n ≥ 06. The machine is based on our second approach to this recognition problem, sweeping back and forth across the input and crossing out
0–1 pairs.
example 41
We want to build a Turing machine that will recognize S = 50
n
1
n
0 n ≥ 06. We will
use one additional special symbol, call it X, to mark out (“erase”) the 0s and 1s
already examined. Thus the tape alphabet is I = 50, 1, b, X6. State 6 is the only
final state. The quintuples making up T are given below. Each quintuple or group
of quintuples has a “comment” describing its function. Just like well-written comments in computer code, this makes the Turing instructions much easier to understand. Be sure to include comments in any Turing machine definition.
(0, b, b, 6, R)
Recognizes the empty tape, which is in S.
(0, 0, X, 1, R)
Erases the leftmost 0 and begins to move right.
(1, 0, 0, 1, R)
(1, 1, 1, 1, R)
(1, b, b, 2, L)
(1, X, X, 2, L)
(2, 1, X, 3, L)
Erases the rightmost 1 and begins to move left.
(3, 1, 1, 3, L)
Moves left over 1s.
(3, 0, 0, 4, L)
Goes to state 4 if more 0s are left.
(3, X, X, 5, R)
Goes to state 5 if no more 0s in string.
(4, 0, 0, 4, L)
Moves left over 0s.
(4, X, X, 0, R)
Finds left end of binary string and begins sweep again.
(5, X, X, 6, R)
No more 1s in string; machine accepts.
Reading down the columns in Figure 9.18, we can see the key configurations (skipping some routine steps) in the machine’s behavior on the tape
b
...
0 0 0 1 1 1 b ...
which, of course, it should accept.
∂
Moves right in state 1 until it reaches the end of the binary
string; then moves left in state 2.