 is seen that the TM halts at step 14. The output tape then contains the string 1111100 = 5, which is the expected result. It is left to the reader as an exercise to show that the program also works with other integer choices, meaning that this is a true adding machine! We note that the program only requires four states with two symbols, which illustrates its simplicity. The output state S5, which is undefined, forces the TM to halt. Analyzing the tape moves line by line in Table 7.4, we can better understand how the algorithm works. Basically, each time the head sees a 1 in the cell, the only action is to look at the next cell to the right, and SO on, until a 0 input is hit (here, at step 3). The head then inspects the next cell with input state S3. If the result is another 0, then the output state is S5, meaning that the machine must halt at the next step, the output tape remaining as it is. This is because reading two successive 0 means that either (a) the second operand is equal to zero, or (b) that the addition is completed. If the result is a 1, then the program flips the two cell values from 01 to 10, and the same inspection as before is resumed, until another 0 is hit (here, at step 12). If the sequence 00 is identified from there, the TM halts, meaning that the addition is completed. 7.2 The Turing machine Table 7.4 Tape changes during Turing machine computation, using the action table in Table 7.3, which defines the addition of two numbers. The input tape is set 1101110, which in unary corresponds to the two numbers 2 = 11 and 3 = 111, as delimited by the blank symbol 0. The initial position of the head is on the leftmost bit. The output tape is seen to contain the string 1111100 = 5. Input state Tape contents Output state 1101110 1101110 1101110 1101110 1100110 1110110 1110110 1110010 1111010 1111010 1111000 1111100 1111100 1111100 Performing the addition of large numbers only increases the number of computation steps and the overall computation time. But since the tape is infinite, there is no problem