These values are
1 the current state
2 the current symbol being read
3 the symbol with which to replace the current symbol
4 the next state to enter
5 the direction to move the tape (Right, Left, or Stationary)
As a first example, suppose a TM includes these three instructions (??† means blank):
1 (1, 0, 1, 1, Right )
2 (1, 1, 0, 1, Right )
3 (1, ??†, ??†, halt, Stationary)
The first says that if the symbol being read is a 0, replace it with a 1 and move right. The second says that
if the symbol being read is a 1, replace it with a 0 and move right. The third says that if the symbol being read
is a blank, halt the machine without moving the tape.
Assume the tape presented to this TM contains the symbols:
1 1 0 1 0 1 0 0 ??† ??† ??†...
Starting in state 1, and positioned at the extreme left of the tape, the machine reads the symbol 1. Instruction
2 applies to this situation, so the instruction causes the 1 to be replaced by a 0, the machine state to remain 1,
and the machine to move 1 cell to the right on the tape.
Next the TM reads another 1. Instruction 2 applies again, so the TM changes the second 1 to a 0, and moves
right again, remaining in state 1.
When the TM reads the symbol 0, instruction 1 applies, so instruction 1 causes the 0 to be replaced by a 1,
the machine to stay in state 1, and the machine to move right once again.
Pages:
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78