Cellular Automata

Take a strip of graph paper. Colour some squares black. Now apply one tiny rule, over and over: each square looks at itself and its two neighbours, and from just those three squares decides its next colour. That's the entire machine — no memory beyond the strip, no central control, no square knowing anything about the big picture. You would expect wallpaper: dull, repetitive patterns. What you actually get — from certain rules — is fractals, apparent randomness good enough to ship in commercial software, and, astonishingly, full-blown computers. A cellular automaton (CA) is this idea made precise, and it is one of the clearest demonstrations in all of science that enormous complexity needs no complicated ingredients.

The recipe

Every cellular automaton is built from the same four ingredients:

A grid of cells — a 1-D row, or a 2-D board like a two-dimensional array.
A finite set of states per cell — often just two: alive/dead, black/white, 1/0. Each cell is a tiny finite-state machine.
A neighbourhood — which nearby cells a cell can "see" (itself and its two flanking cells in 1-D; the 8 surrounding cells in 2-D).
One local update rule, the same for every cell, applied to all cells simultaneously: new state = rule(what my neighbourhood looks like now).

Time ticks in generations: from the whole grid at time t, the rule computes the whole grid at time t+1. Everything that ever happens in a CA universe — every pattern, every structure — is just this one rule, everywhere, forever.

The 256 elementary universes

Start with the simplest possible setting, championed by Stephen Wolfram: one row of two-state cells, each seeing itself and its immediate left and right neighbours. A neighbourhood is then 3 bits, so there are 2^3 = 8 possible neighbourhood patterns, from 111 down to 000. A rule must assign one output bit to each of the 8 patterns — so there are exactly 2^8 = 256 possible elementary cellular automata. Better still, the 8 output bits, read as a binary number, give each rule its name. Here is Rule 90, so called because its outputs spell 01011010_2 = 90:

neighbourhood	111	110	101	100	011	010	001	000
new centre cell	0	1	0	1	1	0	1	0

Stare at that table and a pattern pops out: the new cell is 1 exactly when the left and right neighbours differ. Rule 90 is simply XOR of the two neighbours (the centre cell is ignored!). Run it from a single black cell and it draws the Sierpiński triangle — an infinite fractal, from one line of arithmetic. Its neighbour Rule 110 (outputs 01101110_2) looks scarcely more elaborate on paper, yet produces an endless boiling froth of interacting structures — and, as we'll see below, that froth can compute. Rule 30, meanwhile, churns out chaos so convincingly random that Wolfram's own Mathematica software used it for years as a random-number generator.

Run one yourself

Sixteen generations of Rule 90 from a single 1, in a dozen lines. The heart of it is the line that looks up the output bit: the 3-bit neighbourhood becomes a number from 0 to 7, and shifting the rule number right by that amount exposes the answer bit. Change rule to 110 or 30 and run it again — same code, wildly different universe:

const width = 33; const rule = 90; // try 110, 30, 184… let cells: number[] = new Array(width).fill(0); cells[Math.floor(width / 2)] = 1; // one lit cell in the middle const show = (row: number[]): string => row.map((c) => (c ? "█" : "·")).join(""); for (let gen = 0; gen < 16; gen++) { console.log(show(cells)); const next: number[] = new Array(width).fill(0); for (let i = 0; i < width; i++) { const left = cells[(i + width - 1) % width]; // wrap around the edges const centre = cells[i]; const right = cells[(i + 1) % width]; const pattern = left * 4 + centre * 2 + right; // 0…7 next[i] = (rule >> pattern) & 1; // that pattern's output bit } cells = next; }

The triangle-of-triangles you see is Sierpiński's fractal being assembled one row at a time — by cells that each know only their two neighbours.

Conway's Game of Life

In 1970 the mathematician John Conway moved the game to two dimensions and struck gold. In the Game of Life, each cell of a 2-D grid is alive or dead and watches its 8 neighbours. The whole rulebook is four lines (compactly written B3/S23 — "born on 3, survives on 2 or 3"):

a live cell with 2 or 3 live neighbours survives;
a live cell with fewer than 2 live neighbours dies (loneliness);
a live cell with more than 3 live neighbours dies (overcrowding);
a dead cell with exactly 3 live neighbours is born.

From these four lines a whole zoology emerges. Still lifes (like the 2×2 block) never change. Oscillators (like the blinker, three cells in a row) pulse forever with a fixed period. And most famously, the glider — five cells — walks: after four generations it reproduces its own shape exactly, shifted one cell diagonally. Nothing in the rules mentions movement; the glider is a self-sustaining wave of births and deaths that carries its pattern across the board forever. Step through its four-beat stride below.

A grid that computes

Gliders changed everything. A stream of gliders can carry a signal; collisions between glider streams can gate, block or redirect other streams — and out of such collisions people have built AND gates, OR gates, memory, and eventually entire programmable computers living inside Life's grid. The Game of Life is Turing complete: anything any computer can compute, some monstrous Life pattern can compute too. Even more remarkably, Matthew Cook proved (published 2004) that the humble 1-D Rule 110 is Turing complete as well — a universal computer in one row of cells reading three neighbours at a time. This makes cellular automata a genuine model of computation, sitting alongside Turing machines — and a favourite testbed for deeper questions: physicists study CAs whose rules can be run backwards, the reversible cellular automata, as toy universes whose physics never forgets.

Conway's Game of Life (B3/S23) is Turing complete: glider streams and their collisions implement wires, logic gates and memory;
elementary Rule 110 is Turing complete (Cook, 2004) — universal computation in a one-dimensional, two-state, three-neighbour rule;
consequently, almost every global question about such automata ("will this pattern ever die out?") is undecidable — no algorithm can answer it in general.

Life was born low-tech: John Conway and his students at Cambridge tuned its rules by hand, pushing counters around a Go board — tweaking the birth and death thresholds until the game sat on the knife-edge between fizzling out and exploding. When Martin Gardner described it in Scientific American in October 1970, it detonated. Readers burned untold hours of university mainframe time hunting patterns; Gardner later said the column brought him more mail than anything else he ever wrote. Conway had offered $50 for a pattern that grows forever, and within weeks Bill Gosper's team at MIT found the glider gun — an oscillator that fires a fresh glider every 30 generations, forever. That gun became the machine-gun of Life engineering: streams of gliders as signals were the key step towards building computers in the grid. Conway, a world-class mathematician who invented surreal numbers, reportedly grumbled that he would be remembered mainly for a game — history has proved him exactly right, and the game immortal.

The tempting inference: "each cell only sees its nearest neighbours, so nothing in a CA can have long-range effects." The glider demolishes this. Every individual birth and death is decided purely locally — yet the glider, a pattern of such events, travels arbitrarily far, carrying its shape (and hence information) across the entire grid, undimmed, forever. Flip one cell today and the consequences can propagate outward generation after generation without limit — that is exactly how glider signals make Life compute, and why predicting a CA's far future can be as hard as running every step. Locality constrains how fast influence spreads (one cell per generation — a CA has a "speed of light"), but not how far. Small rules, global reach: that is the whole magic of cellular automata, and forgetting it is the classic way to underestimate them.