Difference between revisions of "Universal computer"

From LifeWiki
Jump to: navigation, search
(added universality of 236/35)
(expanded)
Line 1: Line 1:
 
{{Glossary}}
 
{{Glossary}}
A '''universal computer''' in a cellular automaton is a system that can compute anything that a [http://en.wikipedia.org/wiki/Turing_machine 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.
+
A '''universal computer''' in a [[cellular automaton]] is a system that can compute anything that a [http://en.wikipedia.org/wiki/Turing_machine 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==
 
==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. The universal computer uses glider logic and a [[sliding block memory]].
+
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 2000, Paul Rendell constructed a direct implementation of a Turing Machine <ref>{{cite web|url=http://rendell-attic.org/gol/tm.htm|title=A Turing Machine in Conway's Game of Life|author=Paul Rendell|date=April 2, 2000}}</ref>. This computer is infinite, as it requires an infinite length of tape for the Turing Machine.
+
In 2000, Paul Rendell constructed a direct implementation of a Turing Machine.<ref>{{cite web|url=http://rendell-attic.org/gol/tm.htm|title=A Turing Machine in Conway's Game of Life|author=Paul Rendell|date=April 2, 2000}}</ref> 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 <ref>{{cite web|url=http://www.igblan.free-online.co.uk/igblan/ca/|title=Life Universal Computer|author=Paul Chapman|date=November 11, 2002}}</ref>.
+
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.<ref>{{cite web|url=http://www.igblan.free-online.co.uk/igblan/ca/|title=Life Universal Computer|author=Paul Chapman|date=November 11, 2002}}</ref>
  
 
==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>.
+
  
 
==References==
 
==References==
Line 17: Line 16:
  
 
==External Links==
 
==External Links==
 
+
{{LinkLexicon|lex_u.htm#universalcomputer}}
[http://www.argentum.freeserve.co.uk/lex_u.htm#universalcomputer Universal computer] at the Life Lexicon.
+

Revision as of 00:50, 14 May 2009

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 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]

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]

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".

External Links