This is a Turing Machine implemented in Conway's Game of Life.
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 goltm.zip 71Kb To download my old patterns pwrlif.zip 32Kb What's new 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 (
http://www.radicaleye.com/lifepage/patterns/sbm/sbm.html). In 2002 Paul Chapman used this to implemented a complete counter machine that demonstrates universal capability (http://www.igblan.free-online.co.uk/igblan/ca/index.html). A java applet simulating any counter machine and generating a GoL pattern based on Paul Chapmans design is here.
|
Site by Paul Rendell. |
Last Update 7th December 2011 |
Comments to Paul Rendell |