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:
|
State |
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 |
Halt |
– |
D:R, V:1, NS:2 |
Where:
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.