The Turing Machine Program

The program I chose is one that duplicates a pattern of 1's. With 2 1's on the tape to the right of the reading position it takes 16 cycles to stop with 4 1's on the tape. This takes over one hour on my computer.

The state transition table for this program is as:


Input Symbol 0

Input Symbol 1

Input Symbol 2

0 Find next v=1

D:R, V:0, NS:2

D:R, V:2, NS:1

D:L, V:2, NS:0

1 Write 2*v=2

D:L, V:2, NS:0


D:R, V:2, NS:1

2 Convert v=2 to v=1



D:R, V:1, NS:2

D =
Direction of movement of the tape
V =
Value of symbol to write
NS =
next state

 A P240 gun has been placed to insert the instruction "D:L, V:0, NS:0" when the blocking glider is deleted, which it is in the initial pattern above. This starts up the Turing Machine.

You can see this program in operation on a Turing Machine Simulator by Anthony Morphett.

Back to Turing Machine Main Page

Site by Paul Rendell.

Last Update 14 Dec 2009

Comments to Paul Rendell