As the machine advances down the tape, every 1 will be changed to a 0, and every 0 will be changed to
a 1. Finally, the machine will read a blank. In that case, instruction 3 will apply, and the machine will halt.
This simple TM is a machine for complementing (inverting) the bits of a binary number. The result of the
computation will be a tape that contains these symbols:
0 0 1 0 1 0 1 1 ??† ??† ??†...
Complementing the bits of a binary number is a frequently required task, so this is a useful TM.
A slightly more complex task is that of complementing and incrementing a binary number. That operation is
often used by computers to perform binary subtraction. In fact, in the ???old days??? when the only calculating
machines available were mechanical adding machines, people performed subtraction the same way in base 10,
using the 10??™s complement method. To subtract 14 from 17 in base 10, they found the 9??™s complement of 14, which
is 85 (subtract 1 from 9 to get the 8, and subtract 4 from 9 to get the 5). They incremented 85 by 1, to get 86, or
what??™s called the 10??™s complement. Adding 17 and 86 gave 103. Ignoring the carry digit gave the answer of 3!
To perform binary subtraction by the 2??™s complement method, the subtrahend is complemented and
incremented, and then added to the minuend.
Pages:
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79