# Difference between revisions of "Universal computer"

(→Universal computers in other cellular automata: red link removal) |
|||

(7 intermediate revisions by 6 users not shown) | |||

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

==Universal computers in other cellular automata== | ==Universal computers in other cellular automata== | ||

− | David Eppstein and Dean Hickerson proved that [[ | + | 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.<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== | ||

<references /> | <references /> | ||

− | ==External | + | ==External links== |

{{LinkLexicon|lex_u.htm#universalcomputer}} | {{LinkLexicon|lex_u.htm#universalcomputer}} |

## Latest revision as of 12:25, 27 May 2020

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

## References

- ↑ Paul Rendell (April 2, 2000). "A Turing Machine in Conway's Game of Life".
- ↑ Paul Chapman (November 11, 2002). "Life Universal Computer".
- ↑ Nicolas Loizeau (March 10, 2017). "Building a computer in Conway's Game of Life".
- ↑ D. Eppstein. "B35/S236".
- ↑ Tim Hutton. "Rule Table Repository".

## External links

- Universal computer at the Life Lexicon