Rule 30: One Black Cell

A simple program, a forty-year question Start with a single black square. Apply one tiny rule, row after row. What grows is part orderly, part wild, and nobody can yet prove whether the column running straight down its middle ever repeats.

Rule 30 growing from one black cell.

The green column down the middle is the one Stephen Wolfram's prizes ask about. As each row appears, its middle cell is read off into the strip on the right: so far it looks exactly like the tosses of a fair coin. 1 · The rule A rule you could run with a pencil Picture a row of squares, each black or white. To make the next row, every square looks at three squares above it: the one directly above, and that one's left and right neighbours. Those three colours can come in eight combinations, and the rule simply says, for each combination, what colour the new square is. Write the eight answers as a binary number and you get 00011110, which is 30. That is the whole of Rule 30. Below, the rule is applied one square at a time: the three boxed squares decide the new one, and the matching entry of the rule lights up. In words: the new square is black when the square above-left differs from "the square above or the one above-right is black". One line of logic, the same everywhere, applied for ever. 2 · Why it matters Randomness from nothing In the early 1980s Stephen Wolfram set out to look systematically at the simplest possible programs of this kind. There are only 256 of them. Most do something dull: they die out, repeat, or make neat nested patterns.

Rule 30 does not.

Its left side settles into regular stripes, but its right side never settles at all, and its centre column passes the standard tests of randomness. That observation, that a very simple rule can produce behaviour which looks random, became a cornerstone of Wolfram's A New Kind of Science (2002).

For many years Rule 30 generated Mathematica's random integers. Its pattern clads the walls of Cambridge North railway station.

And it was the subject of a challenge.

Seven years on, all three are open. Read the column as a coin, black for heads and white for tails: Problem 1Does the centre column always remain non-periodic? Does the coin ever fall into a pattern that repeats for ever?Open Problem 2Does each colour occur on average equally often in it? Is the coin fair in the long run?Open Problem 3Does computing its nth cell take at least n steps of effort?

Is there a shortcut to the nth toss?Open The coin is not random: every toss is fixed by the rule. So each answer is simply yes or no, and only a proof can settle it.

Wolfram's team has computed a billion cells of the column. They look perfectly random, and that proves nothing.

3 · Order at the edges Where the order is, and where it ends Look again at the pyramid. Its left side is striped and its right side is wild, but neither is quite what it seems. Both edges carry order with an exact shape, and both shapes were found on 9 October 2026 by looking hard at the picture.

The stripes on the left end along a ragged line Read the pyramid in lines parallel to its left edge, its diagonals.

The first few diagonals settle into short repeating patterns, and once a run of them repeats, it repeats for ever, because those diagonals depend only on one another. So at every row there is an exact count of diagonals that have reached their eternal stripes.

Below, they are shaded, and the magenta line is the edge of the shaded band: the exact place where order ends. It does not run down the side of the pyramid.

It starts near the centre at the very top and leans out at about a quarter of the speed of the pyramid's own edge, 0.244 squares per row on average. That is close to the speed, about 0.246, at which a change made on the right spreads leftwards through a random row; whether the two are exactly equal is not known. The chart follows the edge to row 524,288: about that straight line it wanders like a random walk.

Open the left front on its own page → Live: Rule 30 from one black cell to row 512, with the ordered band shaded and its exact edge in magenta; the dashed line is a quarter of light speed.

Sound, off until pressed, turns the chart's curve into one gliding tone, its pitch the curve's height between the two dashed guides. The edge's definition is exact, and the ordered band never shrinks. Its average speed and its random-walk wander are measurements, not proofs. The chart's time axis doubles at each tick, so its last stretch holds half of all the rows: the late climb is an ordinary swing of the walk, not a sudden change. Even the wild side has a ruler at its edge Gareth noticed this by eye: along the wild right edge, the white triangles that touch it arrive at perfectly even spacing, and only their sizes differ.

It is exactly true.

At every second row a white triangle starts one square inside the edge, and its width depends only on how many times 2 divides the row number, like the marks on a ruler.

Rows 2, 6, 10, 14 and so on (twice an odd number) get the smallest triangle, rows 4, 12, 20 the next size up, rows 8, 24, 40 the next, and so on.

The magenta tracer joins the newest triangle's corner to its tick and leaves a trail: inside the edge the trail is the right side's own front, the place where its visible order ends, deepest at each power of 2.

Sound, off until pressed, plays each triangle as a note, an octave lower for each doubling, and keeps its own time: it plays on down the ruler past the end of the picture until you pause it.

Neither kind of order reaches the prize column. At row t the centre column sits on the t-th diagonal from either edge, ever deeper, where the periods have grown too long to see: the 54th diagonal from the right edge repeats only after 4,194,304 rows.

Order at the edges says nothing yet about the middle, and that is why the problems are hard.

4 · The whole picture A triangle, a square and a circle Now to the prize column itself. Problem 1 asks whether it can ever repeat.

So assume it does, in the simplest way it could: white, black, white, black, for ever. Hold the centre to that beat, like a wall, and run Rule 30 on the squares to its right from a random start. The column right next to the wall does something remarkable. It falls into a fixed loop of 56 steps, a wheel, and stays on it until something from further right knocks it off, after which it settles back at a new position on the wheel.

The plate below puts the pieces together, after Leonardo's Vitruvian Man. At the top is the triangle Rule 30 draws from one cell, with the prize column down its middle and the off-centre region where the chaos lives. It is the top half of a square standing on its corner.

Below is the wheel, which is really two clocks at once, of 8 and of 7 positions. Beside it runs the wall experiment that drives it.