Elementary Cellular Automata
One 8-bit rule number, three worlds: flip it to walk a single-line automaton from an ordered fractal through Turing-complete complexity to deterministic chaos.
Level: Beginner
Emergence
Discover how interactions between parts can create properties and behaviors that no individual component possesses alone.
Take the QuizElementary cellular automata: one knob from order to chaos
An elementary cellular automaton is the simplest computer imaginable: a row of 0/1 cells, all updated in lockstep by a single rule that maps each cell and its two neighbours to the next value. There are only 256 such rules — yet among them lies the full range of behaviour Stephen Wolfram catalogued, from frozen order to deterministic chaos.
The one knob is rule_number. Starting from a single centred cell, the
shipped trio walks the regimes:
- Rule 90 — ordered: the self-similar Sierpinski triangle.
- Rule 110 — complex (the default): localized "particles" drift and collide on a textured background. This is Wolfram Class IV, the edge of chaos, and the only elementary rule proven Turing-complete — it can in principle run any computation.
- Rule 30 — chaotic: aperiodic noise whose centre column is so statistically random that Mathematica shipped it as a random generator.
Three probes argue the regime: ones (how full each row is), clusters
(how many distinct structures), and center_fraction (the share of 1s
down the centre column — near 0.5 only for chaos, far from it for order).
from tys import progress, frame, probe
Run an elementary cellular automaton selected by rule_number.
def simulate(cfg: dict):
width = cfg["width"]
steps = cfg["steps"]
rule_number = cfg["rule_number"]Wolfram code: bit i of rule_number is the output for neighbourhood i, where i = 4left + 2center + right (so i runs 0..7).
rule = [(rule_number >> i) & 1 for i in range(8)]
center = width // 2
row = [0] * width
row[center] = 1 # a single live cell, centred so the figure is symmetric
def next_row(cur):
nxt = [0] * width
for i in range(width):
left = cur[i - 1] if i > 0 else 0
mid = cur[i]
right = cur[i + 1] if i < width - 1 else 0
nxt[i] = rule[(left << 2) | (mid << 1) | right]
return nxt
Count runs of consecutive live cells: a proxy for how many distinct structures ("particles") a row holds, rather than just how full it is.
def cluster_count(cur):
runs = 0
prev = 0
for x in cur:
if x and not prev:
runs += 1
prev = x
return runs
rows = []
center_col = []
center_ones = 0
density_sum = 0.0Generations 0..steps, probing each so the last probe and the final grid row describe the same generation (no off-by-one).
for step in range(steps + 1):
rows.append(row)
center_ones += row[center]
center_col.append(row[center])
ones = sum(row)
density_sum += ones / width
probe("ones", step, ones)
probe("clusters", step, cluster_count(row))
probe("center_fraction", step, center_ones / (step + 1))
progress(int(100 * step / steps))
if step < steps:
row = next_row(row)
frame(0, rows)
Smallest period (<= 25) the centre column repeats with over its tail; 0 means no short period was found — the signature of chaos.
tail = center_col[-min(len(center_col), 50):]
center_period = 0
for p in range(1, min(25, len(tail) // 2) + 1):
if all(tail[i] == tail[i - p] for i in range(p, len(tail))):
center_period = p
break
final = rows[-1]
return {
"final_ones": sum(final),
"density": sum(final) / width,
"mean_density": density_sum / (steps + 1),
"center_fraction": center_ones / (steps + 1),
"center_period": center_period,
}
def requirements():
return {
"external": []
}
# order.yaml — Wolfram Class II. Rule 90 draws the self-similar Sierpinski
# triangle: sparse, perfectly predictable.
width: 129
steps: 64
rule_number: 90
| Metric | Value |
|---|---|
| final_ones | 2.00 |
| density | 0.02 |
| mean_density | 0.09 |
| center_fraction | 0.02 |
| center_period | 1.00 |
# complex.yaml — the default. Wolfram Class IV, the edge of chaos. Rule 110
# grows localized particles that drift and collide; it is the only
# elementary rule proven Turing-complete.
width: 129
steps: 64
rule_number: 110
| Metric | Value |
|---|---|
| final_ones | 43.00 |
| density | 0.33 |
| mean_density | 0.15 |
| center_fraction | 1.00 |
| center_period | 1.00 |
# chaos.yaml — Wolfram Class III. Rule 30: fully deterministic, yet its
# output is aperiodic noise (Mathematica's old random-number source).
width: 129
steps: 64
rule_number: 30
| Metric | Value |
|---|---|
| final_ones | 64.00 |
| density | 0.50 |
| mean_density | 0.27 |
| center_fraction | 0.55 |
| center_period | 0.00 |
- What is rule_number, and how does one number define a whole automaton?
- Each cell's next value depends on three cells: itself and its two neighbours. Three binary cells have 8 possible patterns, and rule_number is simply the 8-bit table saying what each pattern maps to — bit i is the output for neighbourhood i = 4·left + 2·center + right. 30 is 00011110, 90 is 01011010, 110 is 01101110: different tables, completely different worlds. There are only 256 elementary rules, and they already span the full range from trivial to chaotic to universal.
- What are the Wolfram classes this walks through?
- Wolfram sorted the 256 rules into four behaviours. Class I dies to a uniform state. Class II settles into stable or repeating structures — Rule 90's Sierpinski triangle (the 'ordered' config). Class III is chaos — Rule 30 (the 'chaos' config), aperiodic and unpredictable. Class IV is the rare boundary between order and chaos that supports persistent interacting structures — Rule 110 (the default). One knob, rule_number, walks between all four.
- How can a deterministic rule produce randomness?
- Determinism means the next state is fixed given the current one — not that it is predictable by any shortcut. Rule 30 mixes neighbours so thoroughly that the only way to know the cell 1000 steps down the centre column is to run all 1000 steps: no formula, no period, no compression. That is deterministic chaos. The center_fraction probe makes the case — for Rule 30 it sits near 0.5, a fair coin, which is exactly why Mathematica used Rule 30's centre column as a random-number source.
- Rule 110 is Turing-complete — what does that mean?
- It means Rule 110 can compute anything a computer can. The drifting structures act like signals, their collisions act like logic gates, and with a cleverly chosen starting row you can assemble a universal machine. Proven by Matthew Cook, it is one of the simplest systems known to be universal: a one-line rule over 0s and 1s is, in principle, a general-purpose computer — and it lives right at the edge of chaos, not in the ordered or chaotic rules around it.
- How do the three probes tell the regimes apart?
- ones (density) rises with disorder: sparse for the ordered fractal, moderate for Rule 110, fullest for chaos. clusters counts distinct runs of live cells — Rule 110 keeps its cells bundled into a *few* persistent particles, while chaos shatters them into many short-lived runs. center_fraction is the randomness test: near 0.5 means the centre column behaves like a coin flip (chaos), while a value pinned near 0 or 1 means it is perfectly predictable (order).