|This article is a stub. You can help LifeWiki by expanding it.|
Wolfram's Rule 110 (or W110) is a 2-state 1D cellular automaton which has been proven to be Turing-complete.
As in all elementary cellular automata, whether a cell in the pattern will be 0 or 1 in the new generation depends on its current value, as well as on those of its two neighbors.
The Rule 110 evolves as follows:
|New state for center cell||0||1||1||0||1||1||1||0|
The name of the rule, as in all elementary cellular automata, is the binary sequence of the new states (01101110); If interpreted as a binary number, its decimal value is 110.
Since Rule 110 has been proven by Matthew Cook in the 1990s to be Turing complete, emulating it in 2D cellular automata is often used as a proof of their Turing-completeness. In 2004, Cook published his proof in Stephen Wolfram's journal Complex Systems. After careful study of gliders, glider reactions, oscillators and other localized structures, Cook succeeded to construct an emulator of the cyclic tag system, known to be computationally universal. His emulator operates in a specific infinite oscillating tiling (agar) with the period of 7. Gliders and other moving objects in Rule 110 don't propagate in empty space, but move through the tiling by periodically disrupting its local structure.
A finite version of Cook's circuitry can be viewed in Golly by running Rule 110 (called W110 in Golly) in a large tube topology with infinite height and the width divisible by 14.
Emulation by other rules
In some isotropic non-totalistic Life-like cellular automata, there is an elementary one-dimensional replicator that replicates according to Rule 110.