Universal computer

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 the totalistic Life-like cellular automaton B35/S236 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]

gollark: *Terrariola writes `print "Hello World!`"*
gollark: Anyway. This means "please do all the work for a project I didn't think about and which wouldn't work and which I don't understand", coming from Terrariola.
gollark: Specifically, the program you run.
gollark: It just terminates some other thing instead.
gollark: Oh dear.

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".
This article is issued from Conwaylife. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.