A Universal Turing Machine For The GoL Turing Machine

This machine does not have to be the smallest possible so the following criteria where chosen. It should be:

  • Easily understandable.
  • The simplest machine that would fit into the limitations of the Turing machine Built in Conway's Game of Life.
  • Have the smallest possible description of the machine it is simulating (machine T).
  • Have the shortest possible running time.
After constructing the machine I found that Golly is so fast that the speed is not that important. It would not be a great problem if it took several times longer and needs to be very much quicker to see any benefit. The most important element is therefore the size of the pattern which is dominated by the length of the tape.

The machine T must have alphabet 0 and 1 and can only have an infinite tape in one direction. This does not restrict machine T's capability in any way as there are well known methods of converting any Turing machine into one with these limitations.

The UTM alphabet is: 0, 1, A, B, C, D, X and M

The tape is initially laid out as follows:

0*,TL,H,TR,(S,T)*,S,CT,(S,T)*,S,0*

Where:

0* is blank tape to the left and right.
TL is machine T's tape contents to the left the read/write head using symbols 0 and 1.
H is machine T's tape contents under the read/write head using 0 and 1.
TR is machine T's tape contents to the right the read/write head using symbols A and B, the marked version of 0 and 1.
S, S symbol X (M when marked) separates machine T's tape from its description and also separates each of the transitions in the description. The marked version (S) is used before the current transition.
T, T, CT   The description of a transition. CT is the current transition, T is the marked form. The format is "V,D,N0,C,N1".
V is the value to write during the transition. Symbols 0 and 1 unmarked (CT, T) and A and B marked (T).
D is the direction to move machine T's read/write head during the transition, 0 for left, 1 for right (A and B when marked).
C is the separator between N0 and N1. Symbol C when unmarked and D when marked.
N0 is the relative position of the next transition to this one, when the symbol under the read/write head is 0.
N1 is the relative position of the next transition to this one, when the symbol under the read/write head is 1.
  N0 and N1 take the form:
0*n    the next transition is the nth to the right of this transition, n can be 0.
1*n the next transition is the nth to the left of this transition.
10 for halt.
Symbols A and B replace 0 and 1 in the marked form.

The UTM starts in state 0 with its read/write head in the marked section, or better, over the leftmost symbol of the current transaction.

The UTM is described by way of state transition diagrams. These show 16 logical states, however in the implementation some of logical states share the same physical state number without a clash. This occurs for W1 and N1, W2 and N2 and W3 and N3 leaving 13 physical states. The symbol at the foot of the arrow is that under the read/write head and the symbols part way along are; the one to write (if different) and the direction of movement of the head.

This machine is preprogrammed into the Java TM simulator with states numbered 1-13 rather than the 0-12 used here and in the GoL machine.

Example Machine T Description

Java TM simulator

Back to UTM page

Site by Paul Rendell.

Last Update 13 February 2010

Comments to Paul Rendell