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).
I am now building a Stack Constructor. A life pattern that will construct stack cells faster than the Turing Machine can use them.
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 Callahans 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 goltm.zip 71Kb
To download my old patterns pwrlif.zip 32Kb
What’s new:
- 17/01/05 I am starting to investigate a stack generator. The first stage is a simple program to assemble life patterns. The format for the input to this program is described here.
- 25/08/00 Added colour annotation to the picture for the OUT Gate and updated In Gate.
- 13/06/00 Added 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.
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 ( 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).
