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

## 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. The universal computer uses glider logic and a sliding block memory.

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

- ↑ Paul Rendell (April 2, 2000). "A Turing Machine in Conway's Game of Life".
- ↑ Paul Chapman (November 11, 2002). "Life Universal Computer".
- ↑ D. Eppstein. "B35/S236".

## External Links

Universal computer at the Life Lexicon.