766
Modeling Arithmetic, Computation, and Languages
b X X 0 1 1 X b
↑
2
b X X X X X X b
↑
6
b X X 0 1 1 X b
↑
1
b X X X X X X b
↑
5
b X 0 0 1 1 X b
↑
0
b X X X X X X b
↑
3
b X 0 0 1 1 X b
↑
4
b X X X 1 X X b
↑
2
b X 0 0 1 1 X b
↑
4
b X X X 1 X X b
↑
1
b X 0 0 1 1 X b
↑
3
b X X 0 1 X X b
↑
0
b X 0 0 1 1 1 b
↑
2
b X X 0 1 X X b
↑
4
b X 0 0 1 1 1 b
↑
1
b X X 0 1 X X b
↑
3
b 0 0 0 1 1 1 b
↑
0
figure 9.18
PrACtiCe 58 For the Turing machine of Example 41, describe the final configuration after processing the
following input tapes:
a.
b
...
0 0 1 1 1 b ...
b.
b
...
0 0 0 1 1 b ...
c.
b
...
0 0 0 0 1 1 b ...
■
Notice how each state of the Turing machine in Example 41 is designed to
accomplish a certain task, as indicated by the comments. The job of state 1, for