Title :
A Universal Turing Machine in Conway´s Game of Life
Author_Institution :
Dept. of Comput. Sci., Univ. of the West of England, Bristol, UK
Abstract :
In this paper we present a Universal Turing Machine build in the Cellular Automaton Conway´s Game of Life. This is an extension of the Turing Machine built previously by the author [10]. It is example of spatio-temporal collision based computation and has infinite tape provided by two stack structures which grow continuously using collision based construction. Two patterns the fanout and takeout are described which are key in solving the routing and synchronization problems. The procedure used to find a viable order of synthesis of the parts in the stack construction is described.
Keywords :
Turing machines; cellular automata; Conway´s game of life; cellular automaton; collision based construction; routing problem; spatio-temporal collision; stack construction; stack structures; synchronization problem; universal turing machine; Delay; Games; Logic gates; Magnetic heads; Sparks; Turing machines; Conway´s Game of Life; Universal Turing Machine;
Conference_Titel :
High Performance Computing and Simulation (HPCS), 2011 International Conference on
Conference_Location :
Istanbul
Print_ISBN :
978-1-61284-380-3
DOI :
10.1109/HPCSim.2011.5999906
