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.