This project proves universal computation in the Game of Life cellular automaton by using a Turing machine construction. Existing proofs of universality in the Game of Life rely on a counter machine. These machines require complex encoding and decoding of the input and output and the proof of universality for these machines by the Church Turing thesis is that they can perform the equivalent of a Turing machine. A proof based directly on a Turing machine is much more accessible. The computational power available today allows powerful algorithms such as HashLife to calculate the evolution of cellular automata patterns sufficiently fast that an efficient universal Turing machine can be demonstrated in a conveniently short period of time. Such a universal Turing machine is presented here. It is a direct simulation of a Turing machine and the input and output are easily interpreted. In order to achieve full universal behaviour an infinite storage media is required. The storage media used to represent the Turing machine tape is a pair of stacks. One stack representing the Turing tape to the left of the read/write head and one for the Turing tape to the right. Collision based construction techniques have been used to add stack cells to the ends of the stacks continuously. The continuous construction of the stacks is equivalent to the formatting of blank media. This project demonstrates that large areas of a cellular automata can be formatted in real time to perform complex functions.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:589121 |
| Date | January 2014 |
| Creators | Rendell, P. |
| Publisher | University of the West of England, Bristol |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://eprints.uwe.ac.uk/22323/ |
Page generated in 0.0021 seconds