Universal computer

A universal computer in a cellular automaton is a system that can compute anything that a Turing machine can compute (another term for this is Turing-complete). 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. 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.

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. Later an improved scalable version was announced in 2021.

Universal computers in other cellular automata

In Life-like cellular automata

For a universal computer to be finite, it must either be given sufficient memory for a computation prior, or employ a universal constructor. For the latter case, it must be able to escape its own bounding box and diamond, so in a non-strobing rule, its rulestring must contain at least one of the birth transitions {1,2,3}, or when isotropic non-totalistic, at least one birth transition in each of the sets {1c,1e,2c,2a,3i} and {1c,1e,2e,2a,3a}, respectively, meaning there is an upper bound of 2¹⁰¹+2¹⁰⁰+(2⁹⁹+2⁹⁸+2⁹⁷)²/2⁹⁹=145*2⁹⁵ INT rules with Turing-complete finite patterns on infinite planes.

For strobing rules, where ~ denotes the absence of a transition, these prerequisite sets are instead {~b1c,~b1e,~b2c,~b2a,~b3i,s7c,s7e,s6c,s6a,s5i} and {~b1c,~b1e,~b2e,~b2a,~b3a,s7c,s7e,s6e,s6a,s5a}.

David Eppstein and Dean Hickerson proved that B35/S236 has a universal computer and universal constructor, using the same method of proof that Conway used to prove that Life is universal.

In multi-state circuitry rules

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

The well-known rule WireWorld allows construction of very small and robust logic gates, triggers, memory banks etc. In September 2004 David Moore and Mark Owen released a Wireworld computer, in which the results of calculations are shown in seven-segment displays by running "electrons". The computer's instruction set is a highly orthogonal RISC architecture. The program, CPU status and data are stored in a bank of 64 16-bit registers. According to the authors, the computer was designed, with the help of many others, between 1990 and 1992. The version of it included in Golly is preprogrammed to compute and display the sequence of prime numbers. Likely this was the first computer in a cellular automaton that looks like a computer from human perspective.

In 2021 Yoel Matveyev released the largest known cellular automation computer called Izhora based on his own 4-state rule FireWorld. It has 256 kilobytes of memory, a 256 × 128 memory-mapped pixel display and a keyboard driven by a Golly script. Its 32-bit CPU uses a single operation, subtract and branch if zero or negative (SUBLEQ), from which all other operations can be synthesized. Examples include 256-bit factorials, primes and Fibonacci numbers. Tools such as an assembler and emulator are provided for programming it.

Other examples of cellular automation computers include a partial emulation of a real-world Picoblaze microcontroller and a custom multicore CPU.

Universality of predecessor-finding

On August 20, 2023, Ville Salo and Ilkka Törmä proved that arbitrary Boolean satisfiability problems could be encoded to problems of finding predecessors of specific patterns, with the corollary that the process of reversing a single iteration (or otherwise proving that a pattern is a Garden of Eden) is computationally universal.

External links

• Turing completeness at Wikipedia
• Universal computer at the Life Lexicon
• Resources pertaining to computation in cellular automata (discussion thread) at the ConwayLife.com forums