This is a Turing Machine implemented in Conway's Game of Life.

Designed by Paul Rendell 02/April/00.

See a detailed picture, the program and a description of the parts. The description also contains links to pictures, patterns to download and Java animation of the parts that make up the touring machine.

A full description of this machine can be found in the book "Collision-Based Computing" edited by Andrew Adamatzky (Springer Verlag; ISBN: 1852335408).

A larger version of this pattern has now been created containing a Full Universal Turing Machine program.

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 : Paul Callahan's page

For Turing Machine info see: The Alan Turing Internet Scrapbook

To down load the pattern tm.lif 95Kb

To download all the patterns on this site 71Kb

To download my old patterns 32Kb

What's new
7/12/11Counter Machine simulator and Generator for Paul Chapman's Life Universal Computer updated to build P1 version as well as P30 version An example of a pattern it produces is a Turing Machine Simulator The Turing machine is described in 5 counters. The last 2 being the tape. It starts with these both as 2 meaning 10001 in binary the middle 0 being inside the machines as the starting condition. It replaces the 0's between the 1's with 1's to leave 11111 all on the left coded as 31 and 0 on the right.
3/12/11P1 version of Paul Chapman's Life Universal Computer. Adds 1+2. Left counter start at 18 (2^1 x 3^2) ends at 8 (2^8 x 3^0).
25/11/11 Added a variant of Paul Chapman's Life Universal Computer to the applet below which simulates a Turing Machine rather than another Counter Machine. The pattern is also here. The pattern for the original is here.
18/11/11Counter Machine simulator and Generator for Paul Chapman's Life Universal Computer (or any other counter machine) added.
21/06/11A version programed with Wolfram's 2 state 3 symbol Turing machine and blank tape created. An image is here. The rle format file is here. The first 13 cycles are shown here diagrammatically.
23/03/11Full Universal Version created. The new stack has been integrated with the Finite State Machine and the Stack Constructor to create a truly universal turing machine.
16/11/10Stack Constructor created. A new stack design with a constructor pattern which adds cells continuously.
02/03/10Universal Version created.
12/01/05I am starting to investigate a stack generator. The first stage is a simple program to assemble life patterns See Stack Constructor.
25/08/00Added colour annotation to the picture for the OUT Gate and updated In Gate
13/06/00Added colour annotation to the picture for the In Gate

I put this pattern together in 1999-2000 mainly using patterns that I created in the 1980's. The basic design has a Universal Turing Machine in mind so design expands easily to 16 states and 8 symbols. I have a design for a Universal Turing Machine which fits in that size. This is the first fully working Turing machine so I made it small, just 3 states and 3 symbols. It takes 11040 generations for one cycle.

I have put an extra FANOUT in the addressing of the finite state machine to give a trace of the operation.

It is a very simple Turing Machine as it is limited to 3 states and 3 symbols. It is shown in this picture starting with a 2 1's on the tape to the right. It will stop with twice this number on the right. The Tape is implemented as 2 stacks and the machine has been provided with 6 stack cells. This can be expanded as required for the calculation. The Finite State machine part is an array of memory cells address by State (Row) and Symbol (Column).

Each memory cell cycle round in 240 generations with a space for a glider every 30 generations. These 8 positions are decoded as DVVVSSSS with the D for direction (1 = Right) first, VVV is the symbol to write on the tape and SSSS is the next state.

The design for this Turing Machine is extendible by expanding the size of the Finite State Machine part and storing different numbers in the memory cells. The maximum size is 16 states and 8 symbols. This is sufficient for a Universal Turing Machine. This has now been down see here.

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.

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 ( In 2002 Paul Chapman used this to implemented a complete counter machine that demonstrates universal capability ( A java applet simulating any counter machine and generating a GoL pattern based on Paul Chapmans design is here.

UTM Page

Stack Constructor Page

Full UTM Page

Counter Machine Simulator

Site by Paul Rendell.

Last Update 7th December 2011

Comments to Paul Rendell