OCA:Rule 54

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