For instance, to subtract 2 from 5, we can complement and increment
2, and add that to 5 to get 3:
010 2 (in base 2: 0 fours, 1 two, 0 units)
101 2 complemented (1s --> 0s; 0s --> 1s)
110 2 complemented & incremented
(adding 001 to 101 --> 110 in base 2)
+101 5 (1 four, 0 twos, 1 unit)
1011 3 (in base 2: 0 fours, 1 two, 1 unit --
ignore the carry bit to the left)
26 ALGORITHMS [CHAP. 2
Since subtraction is often required, a TM for complementing and incrementing a binary number is interesting.
Here are the instructions for such a machine:
1 (1, 0, 1, 1, Right )
2 (1, 1, 0, 1, Right )
3 (1, ??†, ??†, 2, Left )
4 (2, 0, 1, 3, Right )
5 (2, 1, 0, 2, Left )
6 (3, 1, 1, 3, Right )
7 (3, 0, 0, 3, Right )
8 (3, ??†, ??†, halt, Stationary)
Instructions 1 and 2 are the same as for the simpler TM which complemented the bits on the tape.
Instruction 3 will apply when the TM has complemented all the bits and encountered the blank on the right end
of the tape. When that happens, the machine will go into state 2 and move left.
If the machine is in state 2 and encounters a 0, instruction 4 will cause the 0 to be replaced
by a 1, the machine to enter state 3, and move right. Once the machine is in state 3, instructions 6 and
7 will cause the machine to move right without further changing the contents of the tape.
Pages:
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80