Elementary Cellular Automata, Explained

After reading this you can take any rule number from 0 to 255, work out the next row by hand, and know why rule 30 looks random while rule 90 draws a perfect Sierpiński triangle.

What an elementary cellular automaton is

Picture a single row of cells. Each cell is either black (1) or white (0). To make the next row, you look at every cell together with its left and right neighbours, read off that group of three, and decide the new colour of the middle cell. Apply the same decision to every cell, and you have produced row two from row one. Repeat, and the rows stack downward into a triangle of history.

The decision rule is the whole model. A group of three cells has 2^3 = 8 possible patterns, from 111 down to 000. For each of those eight patterns you choose an output bit, 0 or 1. Eight bits gives one byte, so there are 2^8 = 256 distinct rules. That is why you enter a number between 0 and 255.

Here is the hook. Start with a single black cell in the middle of a white row, run rule 30 for a few hundred steps, and the left half looks structured while the right half looks like static. That static is good enough that Mathematica once used the centre column of rule 30 as a random number source. All of it comes from one black cell and a fixed 8-bit table.

When to reach for this model, and when not to

Elementary cellular automata are the cleanest place to see complex behaviour grow from a trivial rule. Use them to build intuition about determinism, sensitivity to initial conditions, and self-similar patterns. They are also a fair sandbox for the question "how simple can a system be and still compute anything?" Rule 110 answers that: it is Turing complete.

Do not use them as a physical model of anything specific without care. A one-dimensional row updating in lockstep is a toy. It will not predict traffic, forest fires, or crystal growth just because the pictures resemble those things. The value is conceptual: you learn what kinds of behaviour a local rule can and cannot produce. If you want a two-dimensional automaton with moving structures, look at Conway’s Game of Life instead.

The update rule, written down

Let s_i^t be the state (0 or 1) of cell i at row t. The new state depends only on three cells above it:

Here R is the rule: a function from the three input bits to one output bit. The three inputs form a binary number from 0 to 7, and that number picks which bit of the rule byte to read. Writing the rule number as N, the output for neighbourhood value n is bit n of N:

The neighbourhood value is just the three cells read as a binary number: n = 4 s_{i-1} + 2 s_i + s_{i+1}. So neighbourhood 101 has value n = 5, and its output is bit 5 of the rule number. That is the entire mechanism. Everything else is bookkeeping about edges and width.

Working out rule 30 by hand

The demo uses the field defaults: rule 30, a single black cell start, on a modest width. Reproduce the first few rows yourself.

Reading the three preset rules

Three rules on the tool cover the range of behaviour Wolfram classified.

Rule 90

Output is the left neighbour XOR the right neighbour, ignoring the centre. Its byte is 01011010. From a single cell it draws the Sierpiński triangle exactly: at row t the black cells sit where the binomial coefficient \binom{t}{k} is odd. This is self-similar and completely predictable.

Rule 30

Byte 00011110. Chaotic: small changes in the start row spread and amplify, and the centre column passes standard randomness tests. Order on one side, noise on the other.

Rule 110

Byte 01101110. Localized structures drift across a patterned background and interact when they meet, like particles colliding. In 2004 Matthew Cook proved rule 110 can emulate any computation, so it is Turing complete.

What the triangle tells you and what it does not

The most useful reading is the density of black cells per row. For rule 90 from a single cell, row t has exactly 2^{b(t)} black cells, where b(t) is the number of 1s in the binary form of t. Check it: row 3 is binary 11, so b = 2 and there are 2^2 = 4 black cells. Row 4 is binary 100, so b = 1 and only 2 black cells. The count drops from 4 to 2 as you cross from row 3 to row 4, which is why the fractal has those sharp empty triangles.

For rule 30 there is no such formula. The black fraction hovers near 0.5 across most rows once the pattern fills out, which is exactly what you want from a randomness source. But "looks random" is not "is random" in any deep sense: the image is fully determined by the first row. Given the rule and row 0, every later cell is fixed. There is no probability anywhere in the model.

Common mistakes

Three errors account for most confusion.

The second mistake is ignoring the edges. A finite width has to decide what a cell at the far left sees to its left. This tool treats off-grid cells as white (0). Some references wrap the row into a ring instead. The two choices give different pictures near the boundary, so a mismatch with a textbook is often just an edge convention, not a bug.

The third mistake is expecting rule 30 to be truly unpredictable. It is deterministic. If you save row 0 and the rule, you can regenerate the exact image on any machine. Reproducibility is a feature here, not a contradiction of the randomness claim.

Related tools on this site

If the one-dimensional row feels limiting, Conway’s Game of Life extends the same local-rule idea to a two-dimensional grid where structures move and collide. For self-similarity of the kind rule 90 shows, but generated from complex arithmetic instead of a bit table, the Mandelbrot Explorer lets you zoom into endless fractal detail. And if you want to see a very different way of building a shape from simple parts, Fourier Epicycles reconstructs a drawing from a sum of rotating circles.

Related tools

3D Geometry Board

Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.

Bézier Curve Playground

Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.

Central Limit Theorem Demo

Sample from any lopsided distribution and watch the averages pile up into a bell curve.

Conway’s Game of Life

Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.

Dynamic Geometry Board

Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.

Fantasy Map Generator

Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.