When
the machine finally encounters the blank on the right again, instruction 8 will cause the machine
to halt.
If the machine is in state 2 and encounters a 1, instruction 5 will cause the 1 to be replaced by a 0, the
machine to stay in state 2, and move left again. This will continue in such manner until the TM encounters a 0,
in which case instruction 4 will apply, as described in the previous paragraph.
Using the binary number 2 as the example again, the TM will create the following contents on the tape as
it executes:
0 1 0 ??† ??† original tape
1 0 1 ??† ??† complementing complete
1 0 0 ??† ??† after executing instruction 5
1 1 0 ??† ??† after executing instruction 4
1 1 0 ??† ??† halted after executing instruction 8
This TM works for many inputs, but not all. Suppose the original input tape were all zeros:
0 0 0 ??† ??† original tape
After the complementing is complete, and all the 0s become 1s, the TM will back up over the tape repeatedly
executing instruction 5. That is, it will back up changing each 1 to 0. In this case, however, the TM will never
encounter a 0, where instruction 4 would put the TM into state 3 and start the TM moving toward the end of the
tape and a proper halt.
Instead, the TM will ultimately encounter the first symbol on the tape, and instruction 5 will command it
to move again left.
Pages:
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81