The important difference is that the program in the Finite State Machine (FSM) is a Universal Turing Machine program. This requires that the program for a specific Turing machine (TM) is provided on the tape. The program provided on the tape is a variant of the program in the Finite State Machine of the Turing Machine in Conway's Game of Life previously described. A version of the Universal Turing Machine program can be found in the Java TM simulator.

The cycle time is 79*240 life generations compared with 46*240 generations for the TM. It take Golly less than a minute on my laptop to complete the 6113 cycles of the UTM corresponding to 62 cycles of the TM encoded on the UTM tape. I used Golly in hashlife mode with hyperspeed set and 8^8 size steps.

This machine is not that small in terms of the number of state (13) or the number of symbols used (8) but it is efficient in the coding the TM program. The TM program is a two symbol version of the symbol string doubling program used before. It has 6 states and uses binary symbols in pairs to represent the 3 symbols used in the old machine. It doubles an initial string of "10" symbols. In this example converting "101010" to "101010101010". For the machine's convenience "0" and "1" appears as both "0" and "1" and in a marked form as "A" and "B". This machine has 7 state transitions which are coded onto the UTM tape in just 54 symbols. It uses a relative indexing system to locate the next transition.

Three glider positions are used to represent binary values of the symbols. The presence of a glider representing "1" and absence being "0". It is convenient to use single letter to represent the 8 values of the 3 bits. The following are used in the Java TM simulator.

The UTM starts with "1ABABAAXBABDBB" on the left stack and "110C11M1000C00M1111C00M1010C11M0010C1M0010C00M" on the right and initial instruction to write "X" to the left and read the "1" from the right to process in state 0. This instruction can be seen as the 3 spaceships travelling up the right side of the Finite State Machine in the initial pattern. These three are the "1"s of the instruction "10110000". Direction ="1" Symbol ="011" and State="0000". The states are numbered 0-12 rather than 1-13 needed for the Java TM simulator.

"A" and "B" are the marked form of "0" and "1" and "D" and "X" are the marked form of "C" and "M". The marked form is used between the TM read/write head position and the current transition.

The machine finishes with "BABABABABABAAXBABDBBXBBADBBXBAAADAAXBBBBDAAXBAB" on the left and "DBBX0010C1M0010C00M" on the right. The stop instruction is "10" . The "1" has been processed as the count to the next transition forward, thus the rest of the transition has been marked. The "0" or more correctly it’s marked form "A" has just been read to stop the UTM.

A trace of each state and symbol that addresses the FSM is produced. It is interesting to run the pattern in Golly and stop it soon after the 116 million life generations needed to complete the program. The resulting pattern fitted to the screen shows the long trace of the 6113 UTM cycles which has moved away from the little dot representing the machine.

The Golly script for building the UTM contains 3 lines which specify the size of the tape, the contents of the tape and the position of the UTM's read/write head. These are the only lines that require changing to build a UTM pattern to run an alternative specific TM. The new data can be tested using the Java TM simulator.

Conway's Game of Life is a cellular automaton. For general information on Conway's Game of Life and links to freeware / shareware to run the patterns on this site see : the Life Wiki

For Turing machine info see: The Alan Turing Internet Scrapbook

As with all Turing machines the tape can be arbitrarily long. In practice the size can be set by the maximum number of cycles the machine will be run. I am still hoping to building a Stack Constructor. A life pattern that will construct stack cells faster than the Turing machine can use them see here. It would be a simple matter to write a script for Golly which would run the pattern stopping periodically to add stack cells.

An alternative design for a universal computing machine is Marvin Minsky's register machine. This stores arbitrary large numbers by pushing blocks into empty space. A design for the registers was constructed in Conway's Game of Life by Dean Hickinson in 1990 ( http://www.radicaleye.com/lifepage/patterns/sbm/sbm.html). In 2002 Paul Chapman used this to implemented a complete register machine that demonstrates universal capability (http://www.igblan.free-online.co.uk/igblan/ca/index.html).