Reduction
Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.
Randomness that has to be earned
A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.
The compass that will not open
Fix the compass at one opening and never change it. That looks like a serious loss — a circle of a given radius through a given point is the compass's whole job — and it turns out to cost nothing at all, for reasons that are arithmetic rather than geometric.
The price of a construction
Three theorems have shown that a compass alone, a straightedge with one circle, and a compass stuck at one opening all reach exactly the points a full set of instruments reaches. None of them said what the journey costs. Émile Lemoine priced every movement of the hand in 1888, and by his count a compass that collapses when lifted — Euclid's — pays twenty-one operations, by Euclid's own method, for what a compass that holds its opening does in four.
No algorithm can read what a program does
Whether a program halts cannot be decided by any algorithm. Henry Rice showed in 1953 that the halting problem is not special: no algorithm can decide any property of what a program does — whether it ever prints a 7, whether it computes the successor function, whether it is a virus — except the two properties that hold of every program or of none. Every one of the 20,736 smallest Turing machines can be checked by hand; the theorem says why that stops.
Dominoes that no algorithm can match
Emil Post's puzzle has no machines and no programs in it: a handful of dominoes, each with a string on top and a string underneath, and the question whether some row of them, repeats allowed, spells the same word along both edges. No algorithm can answer it for every set of dominoes, because a set can be built whose only matches are a machine's run written out twice, one step out of phase — and three dominoes with strings of three characters already need thirty-six in a row before the edges agree.
Named alongside it
The objects these essays reach for when they reach for this one.
Busy beaverCircleCompassComplexityConstructionHalting problemStraightedgeTuring machineUndecidabilityBreadth-first searchComputationConstructible number