State space
Named by 3 essays across 2 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.
Named alongside it
The objects these essays reach for when they reach for this one.
IterationOrbitBinaryCellular automatonCounterexampleDeterminismEntropyExhaustive searchGroup actionInvariantIrrational rotationLocality