tion in the general case, should the algorithm and corresponding action table cover all possible cases, with the TM halting on completion of the task. It is left as an exercise to analyze how such a program can be implemented. This exercise, and the preceding ones, should generate a feeling of intimacy with the basic TM. As we will see, the TM reserves some surprises, and this is why we should enjoy this exploration. Example 7.4 This concerns the operation of multiplication. A TM program performing the multipli- cation of two integers,5 is shown in Table 7.6. The directions of the move are either > (right) or < (left). As in previous examples, the two numbers to multiply and written in the input tape must be expressed in the unary system, with the convention that integer n is represented by a string of n + 1 1s (0 = 11, 2 = 111, 3 = 1111, etc.). Here, I have introduced a supplemental start instruction (1,_,1,_,>) to position the head to the second cell to the right and the TM in input state 1. This instruction ensures that the program can be run with various simulators available on the Internet. It is seen from Table 7.6 that the multiplication program requires as much as 15 states, plus the undefined "halt" state. Also, the TM must be able to handle (or read and write) six different symbols including the "blank" underscore, which corresponds to an absence of read/write action (and is not to be confused with See www.ams.org/featurecolumn/archive/turing_multiply_code.html and the line-by-line comments to ana- lyze the corresponding algorithm. This program can be tested in Turing machine simulators avail- able on the Internet, see for instance: http://ironphoenix.org/tril/tm/, www.turing.org.uk/turing/scrapbook/ tmjava.html, www.cheransoft.com/vturing/index.html. 6 See, for instance: http://ironphoenix.org/tril/tm/, www.turing.org.uk/turing/scrapbook/tmjava.html, WWW. cheransoft.com/vturing/index.html. 7.2 The Turing machine Table 7.6 Action table for Turing machine multiplication program. The table contains 38 ins