Difference between revisions of "Universal computer"
m (moved Universal computer to Universal compooper) 
m (moved Universal compooper to Universal computer) 
(No difference)

Revision as of 20:16, 22 August 2012
A universal computer in a cellular automaton is a system that can compute anything that a Turing machine can compute. A cellular automaton in which such a system exists is called universal. A universal computer may be either infinite or finite, but when combined with a universal constructor, it is assumed to be finite.
Contents
Universal computers in Life
In 1982, John Conway proved in Winning Ways that the Game of Life has a (finite) universal computer, as well as a universal constructor. Proving the universality of a cellular automaton with simple rules was in fact Conway's aim in Life right from the start. The universal computer uses glider logic and a sliding block memory, and the proof of its existence is also outlined in The Recursive Universe.
In April 2000, Paul Rendell constructed a direct implementation of a Turing machine.^{[1]} This computer is infinite, as it requires an infinite length of tape for the Turing Machine.
In 2002, using Dean Hickerson's sliding block memory, Paul Chapman constructed an implementation of a Minsky Register Machine (a machine of the same capability as a Turing Machine), which he extended to a Universal Register Machine, a finite universal computer.^{[2]}
In 2009, Adam P. Goucher built a Spartan universal computerconstructor, which has three infinite binary memory tapes (program tape, data tape and marker tape). This allows data to be stored in linear space, rather than the exponential space that a Register Machine uses.
Universal computers in other cellular automata
David Eppstein and Dean Hickerson proved that 236/35 has a universal computer and universal constructor, using the same method of proof that Conway used to prove that Life is universal.^{[3]}
Tim Hutton has implemented Codd's design for a universal computer in Codd's 8state cellular automaton.^{[4]}
References
 ↑ Paul Rendell (April 2, 2000). "A Turing Machine in Conway's Game of Life".
 ↑ Paul Chapman (November 11, 2002). "Life Universal Computer".
 ↑ D. Eppstein. "B35/S236".
 ↑ Tim Hutton. "Rule Table Repository".
External Links
 Universal computer at the Life Lexicon