OCA:Rule 54
| Rule 54 | |
| View static image | |
| Number | 54 |
|---|---|
| Computation | q⊕(p∨r) |
| Character | Chaotic |
| Black/white reversal | 147 |
| Left/right reflection | 54 |
|
This article is a stub. You can help LifeWiki by expanding it. |
Wolfram's Rule 54 (or W54) is a 2-state 1D cellular automaton notable for emergence of complex structures and suspected by researchers 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 54 evolves as follows:
| Current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| New state for center cell | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
The name of the rule, as in all elementary cellular automata, is the binary sequence of the new states (00110110); if interpreted as a binary number, its decimal value is 54.
The rule is isotropic and exhibits mirror symmetry. All non-empty patterns explode, expanding to both sides with the speed of light. Localized patterns are better seen inside an infinite tiling (agar). The most common "oscillator" in this rule, so-called soliton, may be considered an infinite growth pattern, since it keeps disrupting the oscillation phase of the tiling behind it. Only when the tiling itself is adjusted to each soliton's pulsation (moved by 2 cells) or an even number of solitons is placed inside the natural (..000100010001..) agar, they may be considered normal oscillators.
Question of Turing completeness
There is ongoing research on Rule 54, whose complex behavior resembles Rule 110, which is known to be computationally universal. There are studies on various spaceships, guns, oscillators, and complex reactions in this rule. Glider reactions in this rule are known to be suitable for building logic gates.
Emulation by other rules
An infinitely-long line in HighLife will replicate according to Rule 54. Running HighLife in Golly on a cylinder of width 1 is an alternative way to emulate Rule 54.
External links
- Elementary cellular automaton-Rule 54 at Wikipedia
- Rule 54 at Wolfram Mathworld
- Complete Characterization of Structure of Rule 54, by Genaro J. Martınez et al.
- Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates, by Genaro J. Martınez et al.
- On Soliton Collisions between Localizations in Complex Elementary Cellular Automata: Rules 54 and 110 and Beyond, Genaro J. Martínez, Andrew Adamatzky, Fangyue Chen, Leon Chua