Wolfram's Elementary Cellular Automata: 256 Rules and the Edge of Computation

Definition and encoding

An elementary cellular automaton (ECA) is a one-dimensional, two-state, three-neighbour cellular automaton. The universe is a binary string — each cell holds 0 (white) or 1 (black) — and at each discrete step every cell simultaneously updates based on itself and its immediate left and right neighbours. Because each neighbourhood has 2³ = 8 possible configurations, and a rule must specify one of 2 outputs for each, there are 2⁸ = 256 possible rules. Rule 0 maps every neighbourhood to 0 (all cells die); Rule 255 maps every neighbourhood to 1 (all cells live forever); Rule 30 and Rule 110 sit at opposite ends of the complexity spectrum.

Reading a rule table

To decode rule N, write N in 8-bit binary. The k-th bit from the right tells you what output a neighbourhood of numeric value k produces:

Rule 110 = 01101110₂
neighbourhood: 111 110 101 100 011 010 001 000
output:          0   1   1   0   1   1   1   0

A standard visualisation stacks time downward — row 0 is the initial condition (a single black cell on white is canonical), row 1 is after one step, and so on. Of the 256 rules, many are equivalent under reflection or colour complement; after accounting for both symmetries there are only 88 genuinely distinct rules. Rule 30 and its mirror Rule 86 produce different-looking patterns but the same complexity class; Rule 110 and Rule 137 are mirrors of each other.

Rule 110: proof of universal computation

Matthew Cook proved in 1994 (published 2004 after a legal dispute over release rights) that Rule 110 can simulate a cyclic tag system, a rewriting system known to be Turing complete. Rule 110's spacetime diagrams contain persistent moving structures called particles embedded in a quasi-periodic period-14 background called the ether. Cook's key insight was that particle collisions — roughly 16 distinct interaction types — are rich enough to simulate the tag system's append and delete operations, with the ether acting as a blank tape and particles encoding data symbols. Because any Turing machine reduces to it, the question "does Rule 110 starting from condition X ever produce a 1 somewhere?" is undecidable, equivalent to the halting problem — a striking result for a rule with only 8 binary degrees of freedom.

Rule 184 and traffic flow

Not every notable rule is about chaos or computation. Rule 184 is a minimal model of one-lane traffic: cells represent road segments, state 1 means a car is present, and a car moves right if the next cell is empty, otherwise it stays. The rule correctly reproduces a free-flow phase at density below 0.5, traffic-jam formation above it, shock waves propagating backward through the jam, and conservation of car number throughout — the simplest cellular automaton that exhibits both phases of the fuller Nagel-Schreckenberg traffic model.

Reversible rules and larger neighbourhoods

A CA rule is reversible if every state has exactly one predecessor. Among the 256 elementary rules, only Rule 51 (complement) and Rule 204 (identity) are reversible — Toffoli and Margolus developed the block-CA formalism specifically to construct reversible 2D rules for modelling physical time-reversibility. Wolfram also extended the study to k-color, radius-r rules: for k=2, radius=2 (a five-cell neighbourhood) there are 2³² ≈ 4 billion rules, with the Wolfram code generalising the same way — rule N maps neighbourhood configuration i to bit i of N.

Frequently asked questions

Try it live

Everything above runs in your browser — open Wolfram 1D Cellular Automata and drag the rule slider or jump straight to presets 30, 90, 110, 54, 184, 45, 18 and 150 to see chaos, fractals and computation unfold. Nothing is installed, nothing is uploaded.