OCA:Rule 110
| Rule 110 | |
| View static image | |
| Number | 110 |
|---|---|
| Computation | ¬p∧q∨q⊕r |
| Character | Class 4 |
| Black/white reversal | 137 |
| Left/right reflection | 124 |
|
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
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 cellular automata, there is an elementary one-dimensional replicator that replicates according to Rule 110.[1][2][3]
Emulating it in other rules, such as Conway's Game of Life, requires unit cells of considerable complexity. The following update formula is given on Stephen Wolfram's website: xor(or(p, q), and(p, q, r)), where p is the next cell to the left, q is the cell that is being updated and r is the cell right to it[4]. Following the same notation, if a toggle flip-flop is used to store the current cell's state q, it can be toggled by a signal produced by the following update formula: and(r,(not(and(q,(not p)))), which may at first look more complicated, but actually requires only two and-not gates[5]. Other equivalent formulas and technologies may be used as well, depending on the properties of the rule used to emulate Rule 110.
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
- ↑ AforAmpere (January 14, 2021). Re: Rules with interesting replicators (discussion thread) at the ConwayLife.com forums
- ↑ Stephen Wolfram. "Note (b) for Section 2.1 - "How Do Simple Programs Behave?"". A New Kind of Science 869. Retrieved on January 4, 2022.
- ↑ Yoel Matveyev (November 3, 2020). Re: Fireworld (discussion thread) at the ConwayLife.com forums
External links
- Elementary cellular automaton at Wikipedia
- Rule 110 at Wikipedia
- Matthew Cook's proof of Rule 110's Turing completeness
- "Rule 110" Unit Cell at Game of Life News. Posted by Heinrich Koenig on December 21, 2005.