Rule — 9x

What you are looking at

A single row of cells, each black or white. To make the next row, look at each cell together with its two neighbours — three cells, so eight possible neighbourhoods — and decide whether the cell below is black or white. Eight yes-or-no answers is eight bits, which is one byte, which is a number from 0 to 255. That number is the rule. There are exactly 256 of these universes and this page contains all of them.

Each new row is drawn beneath the last, so time runs downward and the whole history of the universe is one image.

Almost all of the 256 are boring, and their boringness comes in two flavours: they die out to a blank field, or they settle into stripes. What makes the set worth cataloguing is the handful that do neither.

Rule 90 takes a single black cell and produces the Sierpiński triangle — because rule 90 is exactly "the sum of my two neighbours, modulo 2," which is Pascal's triangle in binary. A fractal falls out of an XOR gate.

Rule 30, from the same single black cell, produces genuine mess. The left side develops a regular herringbone; the centre column is so statistically unremarkable that Wolfram Research used it as the random number generator inside Mathematica for years. Nobody has proved that the centre column never becomes periodic.

Rule 110 is the interesting one. It generates a background texture crossed by localised moving structures — gliders — that collide, merge and emit new gliders. In 2004 Matthew Cook proved that these collisions can be arranged to simulate a universal Turing machine. Rule 110 can compute anything computable. Eight bits of rule, and it is a general-purpose computer.

Try this

90 from a single cell: Sierpiński, exactly. Then run 90 from a random row and watch the fractal shatter into a lattice of overlapping copies.
30 from a single cell. Follow the column directly beneath the seed. That column is the sequence Mathematica used to shuffle your data.
110 from a random row — a single cell is not enough to show it off. Look for the narrow diagonal streaks travelling through the striped background and catch two of them colliding.
Stay on 110 and press New random row several times. The gliders turn up somewhere different every time, but the striped background never changes — it belongs to the rule, not to the seed you gave it.
184 from a random row is a traffic model: black cells are cars, and you are watching a jam form and dissolve.
22, 150 and 105 for more fractals; 54 for more gliders; 4, 32 and 0 for how quickly a universe can die.
Hold down the − and + buttons beside the rule number and walk through all 256 in order. It takes about two minutes and it is the fastest tour of complexity theory available. The strip along the bottom of the plate is the rule itself: eight neighbourhoods, each with its result underneath.

Notes

Stephen Wolfram enumerated and classified these in the early 1980s and proposed four classes: uniform, periodic, chaotic, and complex. The fourth class is the small, strange one — Rule 110 and its mirror images — and Wolfram's conjecture that class-four systems are generally capable of universal computation is the seed of the "principle of computational equivalence" that A New Kind of Science is built around.

Note that rules come in families. Reflecting left and right, or swapping black and white, maps each rule onto another that behaves identically. Rule 110 and rule 124 are mirror images; so are 30 and 86; and 110's black-and-white complement is rule 137, which is therefore also Turing complete. The readout panel computes both relatives for whichever rule you are looking at. Of the 256 rules there are only 88 genuinely distinct ones, which makes the catalogue smaller than it looks and its survivors more remarkable.

What you are looking at

Try this

Notes

Further reading