OCA:Rule 110

From LifeWiki
(Redirected from Rule 110)
Jump to navigation Jump to search
Rule 110
Typical pattern in rule 110
Number 110
Character Chaotic
Radiation.png 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.

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 (non-isotropic in one dimension). All non-empty patterns explode, expanding with the speed of light to the left.

Turing completeness

Glider reactions from a random soup inside the tiling in Rule 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

x = 2, y = 3, rule = B2ei3aci4aei5kqr7e/S01c2-kn3ijry4citwy5aeiq 2o$o$2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]]
The period-8 replicator in
B2ei3aci4aei5kqr7e/S01c2-kn3ijry4citwy5aeiq
(click above to open LifeViewer)
x = 2, y = 3, rule = B2ai3aeir4r5ei/S3e5e6i o$2o$o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]]
The period-2 replicator in B2ai3aeir4r5ei/S3e5e6i.
A replicating unit is a t-tetromino, adjacent copies of which are connected.
(click above to open LifeViewer)

In some isotropic non-totalistic Life-like cellular automata, there is an elementary one-dimensional replicator that replicates according to Rule 110.[1][2]

References

  1. toroidalet (December 19, 2020). Re: Rules with interesting replicators (discussion thread) at the ConwayLife.com forums
  2. AforAmpere (January 1, 2021). Re: Rules with interesting replicators (discussion thread) at the ConwayLife.com forums

External links