OCA:Rule 110
Rule 110  


Number  110  

Character  Chaotic 
This article is a stub. You can help LifeWiki by expanding it. 
Wolfram's Rule 110 (or W110) is a 2state 1D cellular automaton which has been proven to be Turingcomplete.
Contents
Definition
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:
Current pattern  111  110  101  100  011  010  001  000 

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 this rule lacks mirror symmetry, it's amphichiral (nonisotropic in one dimension). All nonempty patterns explode, expanding with the speed of light to the left.
Turing completeness
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 Turingcompleteness. 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 nontotalistic Lifelike cellular automata, there is an elementary onedimensional replicator that replicates according to Rule 110.^{[1]}^{[2]}
References
 ↑ toroidalet (December 19, 2020). Re: Rules with interesting replicators (discussion thread) at the ConwayLife.com forums
 ↑ AforAmpere (January 1, 2021). Re: Rules with interesting replicators (discussion thread) at the ConwayLife.com forums