State space
Named by 12 essays across 4 fields — each of them below, with the objects they name alongside it.
Eight rules and a triangle
A row of cells, each one deciding its next state from the three above it. Eight cases, one bit of output each — a rule that fits in a byte, and 256 of them in total. One of those bytes draws Pascal's triangle.
The orbit that must come back
A system with finitely many states has to repeat itself. Poincaré showed the same thing holds when the states are a continuum — almost every starting point returns arbitrarily close to where it began, however complicated the rule, and the argument is the pigeonhole principle with volume in place of counting.
The puzzle that is exactly half solvable
A sliding puzzle sold with two tiles swapped is not a hard puzzle; it is an impossible one, and the proof is a quantity that no slide can change. The same argument, run three times at once, says that one arrangement of a scrambled cube in twelve is reachable.
A road where nobody overtakes
Rule 184 moves every 1 one cell to the right whenever the cell ahead is empty. It is one of only five elementary rules that never change the number of 1s, and that single property turns it into a model of traffic with an exact transition: below half density every jam dissolves, above it jams can never all clear and drift backwards against the flow.
Thirty-one moves from solved
Parity settles which half of a sliding puzzle's arrangements can be reached and is silent about how far away any of them is. Searching every reachable arrangement of the three-by-three tray answers the second question exactly — two arrangements sit thirty-one moves out — and parity turns up again, this time as a law about distance.
Which graphs let the tokens go anywhere
A sliding puzzle is a graph with a token on every vertex but one. Richard Wilson found in 1974 what every such puzzle can reach, and the answer has a surprise in it — the half the tray is stuck with is not a fact about permutations at all, but about the board being two-coloured — and one exception, a graph of seven vertices that reaches exactly 120 of 720.
The rank that remembers every value
Values arrive one at a time, each must be kept or discarded on the spot, and the aim is to keep one whose rank among all of them is low on average. Told only who is leading, the best rule gets 3.87. Shown the values, a rule gets below 2.33 — and how much lower the best possible rule goes is not known, because the rank of what is kept depends on every value seen, and the best rule may need to remember all of them.
A rule that remembers one row back
Only six of the 256 elementary cellular automata can be run backwards, and all six are trivial: shifts, copies and complements. Every interesting rule forgets. But make the new row depend on the row before the current one as well — combine the rule's output with it cell by cell — and every rule, rule 30 included, becomes exactly reversible: run forwards, swap the last two rows, run the same rule again, and the starting row comes back cell for cell. Nothing is lost, and yet the patterns still look as disordered as ever.
Square it and keep the middle
John von Neumann's first generator of random numbers squared a number and kept its middle digits. Followed from every four-digit seed, it never lasts more than 111 steps before a value repeats — a third of what the birthday problem allows a truly random rule — and one seed in five ends at zero for ever. A counter added before each squaring cures the collapse.
A grid of bits whose rank stops at the state
Fill a square grid with a generator's output bits and compute its rank over the field of two elements. Random bits give full rank or one short, in fixed proportions. A generator built from shifts and exclusive-ors gives full rank up to its number of state bits and then never one more — 32 for a 32-bit xorshift, 128 for the lowest bit of xorshift128+ — however large the grid. The test that catches it is decided by a line of linear algebra.
Three hundred thousand outputs of nearly nothing
Start the Mersenne twister from a state with a single 1 among its 19,937 bits and it puts out zeros, then sparse ones, and only after about 340,000 outputs anything that looks random. Every linear generator has such a zeroland around the all-zero state; xorshift128 crosses it in 37 outputs, WELL512 in 44, and the twister's three-word twist makes it the slowest of all by four orders of magnitude.
A second empty square
With one empty square a sliding tray can reach exactly half its arrangements, and the half it misses is guarded by a sign. Leave a second square empty and the guard disappears — every arrangement is reachable, two tiles can be exchanged in four moves, and the far end of the three-by-three tray comes in from thirty-one moves to twenty-four. Searching every tray with every number of holes shows what each extra square of room is worth.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchInvariantIterationParityPermutationCellular automatonDeterminismLocalityOrbitPseudorandomnessBinaryFinite field