A Turing Machine performing a Program
In the text (pp. 157-160), we constructed a machine for calculating the succesor function. Here is a picture of the whole machine, including the input tape, the tape head, and the finite automaton. The crucial part of the atutomaton, i.e. the circuit for the switches and delays, can be constructed as was explained in the text. The job is nothing but a little exercise of truth-functional logic together with a little reasoning and innovation!
Given:
1. right
2.transfer to 1
3. mark
4. left
5. transfer to 4
6. stop
Keep this flow-chart in mind!
Program Finite Automaton (Input, Output, Internal States) Transition Function and Output Function in binary code Find a suitable Truth Function Logical Circuit
The program continues consecutively, except for the instruction of "conditional transfer". Thus, for the internal states, an easy way is to assign the same code as the output code; and as regards the conditional transfer "transfer to k", assign any other code, and consider two cases: (1) the square under scan contains mark (Input 1), or (2) no mark (Input 0); if (1), look at the kth instruction, and if (2), go to the next instruction, and these are the next internal state. Here is the Table for this machine.
program input internal state next state output state 1. right
111 000 111 (right)2. transfer to 1 1 000 111 - 0 000 101 -3. mark
101 110 101 (mark)4. left
110 010 110 (left)5. transfer to 4 1 010 110 - 0 010 011 -6. stop
011 011 011 (stop)@
Last modified November 26, 2002. (c) Soshichi Uchii