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