This is a Fully Universal Turing Machine (UTM) implemented in Conway's Game of Life.


Designed by Paul Rendell 23/March/2011.

The image above on the left is the initial state. The dotted line going up to the right is program for the stack. The image above on the right is after 149 million generations. The line running down to the left in the middle is the trace of each address of the Finite State Machine and is very sparse. The distance this line has moved from the stack is related to the time that Golly was running after the UTM stopped. The length of this line is related to the time the UTM was running.

It is an extension of the Universal Turing Machine in Conway's Game of Life previously described. The main differences are:

  • The stack grows continuously.
  • It has a new 45 degree stack design.
  • The control logic for the stacks have been reworked for the new design.
  • The data for the stack is provided as a string of push instructions rather than pre set in the stack.

The important difference is that the new 45 degree stack and the stack construction convoys.

The cycle time is 96*240 life generations compared with 79*240 life generations for the UTM and 46*240 for the TM. It take Golly about 30 minutes on my laptop to complete the 6113 cycles of the UTM corresponding to 62 cycles of the TM encoded on the UTM tape plus the 61 push cycles required to program the stack. I used Golly in hashlife mode with 8^8 size steps.

Surprisingly the fixed stack version of this UTM pattern (557 KB) runs quicker in Golly than the old stack design. This might be due to the 45 degree stack. The paths of the gliders in the stack are aligned exactly from one stack cell to another improving hashlife's efficiency.

I have made a version with the P450 C/5 diagonal rakes however this is very large (10.3 MB) and runs very slowly in Golly. The initial population of 3.3 million live cells becomes 336 million after 93 million generations which is as far as I have run it to date. The image in the left is the initial state. The dotted line going up to the right is program for the stack. The image on the right bellow is after 47 million generations. The stem of the "T" running down to the left is the trace of each address of the Finite State Machine and is very sparse.






Turing Machine Main Page

UTM Page

Stack Constructor Page

Counter Machine Simulator


Site by Paul Rendell.

Last Update 27th March 2011

Comments to Paul Rendell