Difference between revisions of "Universal computer"

From LifeWiki
Jump to: navigation, search
m (Universal computers in Life)
(The Rule Table Repository has moved to github.)
 
(3 intermediate revisions by 3 users not shown)
Line 13: Line 13:
 
==Universal computers in other cellular automata==
 
==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.<ref>{{cite web|url=http://www.ics.uci.edu/~eppstein/ca/b35s236/|title=B35/S236|author=D. Eppstein}}</ref>
 
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.<ref>{{cite web|url=http://www.ics.uci.edu/~eppstein/ca/b35s236/|title=B35/S236|author=D. Eppstein}}</ref>
 +
 +
Tim Hutton has implemented Codd's design for a universal computer in Codd's 8-state cellular automaton.<ref>{{cite web|url=https://github.com/GollyGang/ruletablerepository/wiki/CoddsDesign|title=Rule Table Repository|author=Tim Hutton}}</ref>
  
 
==References==
 
==References==

Latest revision as of 22:24, 9 July 2015

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.

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 computer-constructor, 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 8-state cellular automaton.[4]

References

  1. Paul Rendell (April 2, 2000). "A Turing Machine in Conway's Game of Life".
  2. Paul Chapman (November 11, 2002). "Life Universal Computer".
  3. D. Eppstein. "B35/S236".
  4. Tim Hutton. "Rule Table Repository".

External Links