ontent (namely, 1 or 0) is to be written into the cell; (b) In what direction the tape should be moved, namely, left or right; (c) Into what new state Sj the machine should be moved. For instance, given the input state S1 the corresponding instruction could be: (a) If reading 0 then write 1, (b) Move tape to the left, (c) Go into state S3. If the cell reading is 0, the machine changes the contents, then moves according to the two other actions, (b) and (c). If the cell reading is 1, then it halts. To cover this other possibility, a second instruction can be introduced into the action table, for instance; (a) If reading 1 then write 0, (b) Move tape right, (c) Go into state S2. These two sets of instructions in the action table can be summarized as follows: S1;0->1 1; L;s (7.1) s1;1->0;R;s2. Since the instructions move the TM into new states S2, S3, the instructions corresponding to input states S2, S3 should also be found in the table. There are no restrictions concerning 7.2 The Turing machine Table 7.1 Example of action table for Turing machine. Input state Change of cell contents Move tape (R, right; L, left) Output state Table 7.2 Tape changes during Turing machine computation, using the action table defined in Table 7.1. The input tape is blank, representing a string of 0 bits or 0000000 initial position of the head is on the leftmost zero bit. At each step, the position of the head on the tape is shown by the bold, underlined bit. The machine halts at step 6, leaving the codeword 1101100 on the output tape. Input state Tape contents Output state 0000000 1000000 1100000 1101100 the possibility of returning to a state previously used as an input (e.g., s1;0-1;R;s1). If there is no output state corresponding to the instruction, the machine halts. The same happens if the cell reading is not a case covered by the action table given a new input state. To summarize, the tape and machine keep on moving, as long as the combination of initial state and cell reading have a matching definition in the action table. The 