Elementary cellular automata

Eight cases, one byte

A cell's next state depends on three cells: its left neighbor, itself and its right neighbor. Three bits give eight possible neighborhoods, and a rule is just the list of eight outputs — one byte. Stephen Wolfram's numbering reads that byte as a number from 0 to 255: write the neighborhood as a binary number k and the new state is bit k of the rule number.

Rule 30 is 00011110 in binary. Reading the icons in the lab from 111 down to 000, the outputs are 0, 0, 0, 1, 1, 1, 1, 0; algebraically, rule 30 sets each cell to left XOR (center OR right). Mirroring a rule left to right or swapping 0 and 1 gives an equivalent rule (rule 30 mirrored is rule 86), which leaves 88 essentially different rules out of 256.

1. Start from one row: a single live cell in the middle, or random cells with the chosen density.
2. For every cell, compute k from the previous row and look up the new state. All cells update at once.
3. Repeat for the chosen number of steps, drawing each new row under the last.

Four rules worth trying

• Rule 30 grows a triangle whose left side is regular and whose right side looks random, from a completely regular start. Wolfram proposed its center column as a pseudo-random bit source. It is the standard example of a simple deterministic rule producing complex output.
• Rule 90 sets each cell to left XOR right. From a single cell it computes Pascal's triangle modulo 2, so the diagram is a Sierpiński triangle; after t steps the number of live cells is 2 raised to the number of 1s in the binary form of t.
• Rule 110 produces persistent structures that move and collide against a periodic background. Matthew Cook proved (published in 2004) that it is Turing-complete: with a suitable, very long initial row it can emulate any computation. Try it from a random start to see the structures.
• Rule 184 is a minimal traffic model: read a 1 as a car, and a car moves one cell to the right if that cell is empty. The number of cars never changes on a ring. Below density 1/2 every jam eventually dissolves and all cars flow; above it, jams persist and the empty spaces flow backward.

Wolfram sorted the rules by behavior into four qualitative classes: rows that die to a uniform state, rows that settle into fixed or periodic structures, apparently random (chaotic) rows, and complex localized structures such as rule 110's. The classes describe typical behavior from random starts; they are not sharply defined, and some rules sit between them.

Density, distinct rows and periodicity

The lab reports the fraction of live cells in the last row, how many different rows appeared, and whether any row repeated. Because every row determines the next one, the first repeated row means the pattern is periodic from then on, with period equal to the gap between the two occurrences.

On a ring of W cells there are only 2^W possible rows, so every run must repeat eventually. For 201 cells that bound is astronomically large: rules like 30 or 110 will not repeat within any feasible run, while simple rules repeat within a few steps (rule 204 copies the row unchanged, rule 170 shifts it one cell, returning after W steps). "No repeat" therefore means no repeat within the steps simulated, not proof of aperiodicity.

The edges matter once the pattern reaches them. With a single starting cell the pattern spreads at most one cell per step in each direction, so for the first half-width of steps the ring and the dead-edge boundary give identical diagrams.

Example result

Rule 30 from a single live cell on a 201-cell ring: after 100 steps the triangle spans the whole row, and the last row has 103 live cells, a density of 0.512. All 101 rows are different (no repeat); the rule in binary is 00011110.

Implementation

The page runs simulation.js from the package below; the Python file is a line-by-line port with the same random-number generator, so a given seed produces the same result in both languages. The excerpts show the core of each.

// Wolfram's numbering: the three cells (left, center, right) above a cell form a

// number k = 4·left + 2·center + right from 0 to 7, and bit k of the rule number

// is the cell's new state. Rule 30 = 00011110 in binary, so 111 → 0, …, 001 → 1.

export function stepRow(row, rule, wrap) {
  const W = row.length;
  const next = new Uint8Array(W);
  for (let x = 0; x < W; x++) {
    const l = x > 0 ? row[x - 1] : wrap ? row[W - 1] : 0;
    const r = x < W - 1 ? row[x + 1] : wrap ? row[0] : 0;
    const k = 4 * l + 2 * row[x] + r;
    next[x] = (rule >> k) & 1;
  }
  return next;
}

def step_row(row, rule, wrap):
    """Wolfram numbering: k = 4*left + 2*center + right; bit k of the rule is the new state."""
    W = len(row)
    nxt = [0] * W
    for x in range(W):
        l = row[x - 1] if x > 0 else (row[W - 1] if wrap else 0)
        r = row[x + 1] if x < W - 1 else (row[0] if wrap else 0)
        k = 4 * l + 2 * row[x] + r
        nxt[x] = (rule >> k) & 1
    return nxt

Run the full model from a terminal:

node simulation.js --rule 30 --width 201 --seed 42
python simulation.py --rule 30 --width 201 --seed 42

Download the model

Assumptions & limitations

• Finite row. The theory of elementary automata is usually stated on an infinite line. The lab uses a ring (the ends are neighbors) or dead cells beyond the edges; both change the pattern once it reaches the boundary.
• Synchronous, deterministic update. Every cell updates at once from the previous row. Randomness enters only through the initial row, drawn with a seeded generator.
• Nearest neighbors, two states. Larger neighborhoods or more states give far more rules; elementary automata are the smallest nontrivial family.
• Periodicity is checked by exact comparison of whole rows, and only within the simulated steps.

Related simulations

• OS-022Game of LifeTwo rules on a grid of cells: gliders, guns, oscillators and soups that settle or keep going.
• OS-026Forest fire modelTrees grow, lightning strikes, fires spread: a cellular automaton with fires of every size.
• OS-012Random walkCoin-flip steps on a line or grid: distance grows like √n, and in 1-D and 2-D every walker comes back.
• OS-014Markov chainA process that remembers only its current state: stationary distribution, mixing and absorption, live.

Background: Pseudo-Random Numbers and Seeds in Simulation

References

1. Wolfram, S. (1983). Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3), 601–644. doi.org/10.1103/RevModPhys.55.601
2. Cook, M. (2004). Universality in elementary cellular automata. Complex Systems, 15(1), 1–40.