About Wolfram Elementary Cellular Automata
Elementary cellular automata (ECA) are the simplest class of one-dimensional, two-state cellular automata: each cell is either 0 or 1, and its next state depends only on its current value and the values of its two immediate neighbours. Because a cell and its two neighbours form a 3-bit neighbourhood with 8 possible patterns, and each pattern can map to 0 or 1, there are exactly 2⁸ = 256 possible rule tables — numbered 0 to 255 in the Wolfram classification. Despite this extreme simplicity, Stephen Wolfram's exhaustive study in A New Kind of Science (2002) revealed that some rules produce behaviour of astonishing complexity: Rule 30 generates output so irregular it is used as a random-number source inside Wolfram's Mathematica; Rule 110 was proved Turing-complete by Matthew Cook in 2004, meaning it can in principle simulate any computation.
This simulator renders all 256 rules as 2D space-time diagrams (rows = generations, cells = columns). You can select any rule number, toggle the initial condition (single-cell seed or random), adjust the grid width and speed, and observe how local uniformity (Rules 0, 255), periodicity (Rules 1–4), fractal self-similarity (Rule 90 — the Sierpiński triangle), and apparent randomness (Rule 30) all emerge from the same three-cell neighbourhood logic.
Frequently Asked Questions
Why are there exactly 256 elementary cellular automaton rules?
A cell's next state depends on the 3-bit pattern formed by itself and its two neighbours. There are 2³ = 8 such patterns (000 through 111), and each can independently map to 0 or 1. The complete mapping — a lookup table of 8 bits — is therefore one of 2⁸ = 256 possible tables. Wolfram numbers each rule by interpreting its 8 output bits as a binary number: Rule 110 has binary output 01101110, which equals 110 in decimal.
What makes Rule 110 special compared with other rules?
Rule 110 is the only elementary cellular automaton (and one of very few simple rules anywhere) proved to be computationally universal — capable of simulating any Turing machine given an appropriate initial configuration. Matthew Cook published this proof in 2004 after a 15-year embargo by Wolfram. The proof constructs gliders (persistent moving patterns) that act as data and signals, and uses collisions between them to implement logical gates. This makes Rule 110 a minimal substrate for universal computation.
Why does Rule 90 produce the Sierpiński triangle?
Rule 90's update rule computes the XOR of a cell's two neighbours (ignoring the cell itself). Starting from a single "on" cell, this is equivalent to computing Pascal's triangle modulo 2 — and by Lucas's theorem, the entry in row n column k of Pascal's triangle is odd if and only if k is a bitwise subset of n. The resulting pattern of odd/even entries is precisely the Sierpiński triangle, a fractal with Hausdorff dimension log₂3 ≈ 1.585.
How is Rule 30 used as a random number generator?
Rule 30, starting from a single live cell, produces output so irregular that it passes standard statistical tests for randomness. Wolfram's Mathematica uses the central column of a Rule 30 automaton as a pseudorandom bit source (the function RandomInteger[] historically used this). Unlike LFSR-based generators, Rule 30 has no known short-period structure; however, it is deterministic and therefore not suitable as a cryptographic RNG — an attacker who reconstructs the full cell row can predict future output.
What are Wolfram's four classes of cellular automaton behaviour?
Wolfram categorised all ECA rules into four qualitative classes based on their long-term behaviour from random initial conditions. Class 1: evolution to a uniform fixed state (e.g., Rules 0, 255). Class 2: stable or periodic simple structures (e.g., Rule 4, Rule 108). Class 3: chaotic, seemingly random patterns (e.g., Rule 30, Rule 45). Class 4: complex localised structures and interactions — the only class capable of universal computation (e.g., Rule 110). These classes are analogous to fixed-point attractors, limit cycles, strange attractors, and complex dynamical systems respectively.
Can a 1D cellular automaton simulate physics?
Several ECA rules exhibit analogs of physical phenomena. Rule 54 and Rule 110 support gliders (soliton-like structures) that propagate and scatter. Rule 90 with periodic boundaries models quantum-mechanical interference patterns. More practically, Lattice Boltzmann methods — used in fluid dynamics simulation — are higher-dimensional, multi-state generalisations of cellular automata that provably recover the Navier-Stokes equations in the continuum limit, and are widely used in computational fluid dynamics for complex geometries.
Is there a rule that is its own complement?
Yes — several rules are self-complementary (swapping all 0s and 1s produces the same pattern) or are colour-symmetric. For example, Rule 51 simply flips every cell every generation (a trivial complement). More interestingly, Rule 105 is the complement of Rule 150. The full symmetry group of the 256 rules under complementation, reflection, and conjugation generates equivalence classes that reduce the 256 rules to 88 qualitatively distinct behaviours.
How many rules are Turing-complete?
Among the 256 elementary rules, only Rule 110 has been rigorously proved Turing-complete (Cook, 2004). Rule 124, 137, and 193 are conjugates or mirrors of Rule 110 and inherit its universality. Whether other class-4 rules (such as Rule 54) are Turing-complete remains an open question. Beyond ECA, two-dimensional automata like Conway's Game of Life are long-known Turing-complete, and even some one-dimensional two-colour three-state rules have been proved universal.
What happens when ECA rules are run on a ring (periodic boundary) instead of an infinite tape?
With periodic (toroidal) boundary conditions the automaton's state space is finite: there are 2ⁿ possible configurations for an n-cell ring, so the system must eventually cycle. For most rules the transient is short and the eventual period is a small fraction of 2ⁿ. Some rules that appear chaotic on an infinite tape become perfectly periodic on even modestly-sized rings. This distinction between finite and infinite behaviour is important when using ECA for pseudorandom number generation or studying emergent complexity.
What is the connection between Rule 90 and Pascal's triangle?
Starting Rule 90 from a single live cell at position 0, the value of cell k at generation n equals the binomial coefficient C(n, k) modulo 2. By Lucas's theorem, C(n, k) ≡ 1 (mod 2) if and only if every bit of k is also a bit of n (k is a bitwise AND subset of n). This is the exact condition for a cell to be coloured in the Sierpiński triangle. The fractal therefore emerges naturally from the modular arithmetic of Pascal's triangle, a connection first noted by Édouard Lucas in 1878, long before cellular automata were formalised.
Can two different rules produce identical space-time diagrams?
Yes, through the symmetries of complementation and left-right reflection. Reflecting a rule's neighbourhood mapping gives its "mirror rule"; swapping 0s and 1s gives its "complement rule"; applying both gives its "conjugate". These four operations partition the 256 rules into 88 equivalence classes. Rules within the same class produce patterns that are reflections, negatives, or reflected negatives of each other — visually different but structurally identical. For example, Rules 2, 16, 64, and 128 form one such class, all producing very sparse, simple structures.