Difference between revisions of "Universal computer"

From LifeWiki
Jump to navigation Jump to search
(→‎Universal computers in Life: mention Coban's 8-bit computer)
m (→‎Universal computers in Life: later Turing machine versions)
Line 10: Line 10:
  
 
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.
 
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.
 +
 +
In 2010, Paul Rendell completed a [[universal Turing machine|universal version]] of his Turing machine pattern, followed in 2011 by a [[fully universal Turing machine|fully universal]] version, removing the previous requirement (needed for true universality) that the initial Life pattern must have unbounded size and infinite population.
  
 
In 2016, [[Nicolas Loizeau]] created an [[8-bit programmable computer]] pattern, using only four basic parts: a [[twogun|period 60 glider gun]], a [[buckaroo|90° glider reflector]], a [[glider duplicator|p30 glider duplicator]], and a [[eater1|glider eater]].<ref>{{cite web|url=https://www.conwaylife.com/forums/viewtopic.php?p=84641#p84641|title=Building a computer in Conway's Game of Life|author=Nicolas Loizeau|date=March 10, 2017}}</ref>
 
In 2016, [[Nicolas Loizeau]] created an [[8-bit programmable computer]] pattern, using only four basic parts: a [[twogun|period 60 glider gun]], a [[buckaroo|90° glider reflector]], a [[glider duplicator|p30 glider duplicator]], and a [[eater1|glider eater]].<ref>{{cite web|url=https://www.conwaylife.com/forums/viewtopic.php?p=84641#p84641|title=Building a computer in Conway's Game of Life|author=Nicolas Loizeau|date=March 10, 2017}}</ref>

Revision as of 17:49, 30 October 2019

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.

In 2010, Paul Rendell completed a universal version of his Turing machine pattern, followed in 2011 by a fully universal version, removing the previous requirement (needed for true universality) that the initial Life pattern must have unbounded size and infinite population.

In 2016, Nicolas Loizeau created an 8-bit programmable computer pattern, using only four basic parts: a period 60 glider gun, a 90° glider reflector, a p30 glider duplicator, and a glider eater.[3]

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.[4]

Tim Hutton has implemented Codd's design for a universal computer in Codd's 8-state cellular automaton.[5]

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. Nicolas Loizeau (March 10, 2017). "Building a computer in Conway's Game of Life".
  4. D. Eppstein. "B35/S236".
  5. Tim Hutton. "Rule Table Repository".

External links