Concept
Undecidability
The property of a question for which no algorithm gives the right answer on every input.
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
The rule that computes
One of the 256 elementary rules can run any program. Not simulate one, not approximate one — a machine that can compute anything computable, built from a lookup table with eight rows and nothing else.
The question nobody can answer
Halve it if it is even, triple it and add one if it is odd. Every number anyone has tried comes down to one. Nobody can prove they all do, and the reason is not that the problem is hard to state.
Named alongside it
The objects these essays reach for when they reach for this one.
IterationCellular automatonCollatzComputationGliderHalting problemHeuristicLocalityLogarithmOpen problemOrbitParity