Matpic
mathematics, in pictures
Concept

Undecidability

The property of a question for which no algorithm gives the right answer on every input. It is a statement about every possible algorithm, and it is established by self-reference rather than by exhausting the possibilities.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

Elementary cellular automaton, rule 110. A row of cells evolving downward, each cell decided by the three above 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.

dynamics · Cellular automata The Collatz orbit of 27. Halve an even number, triple an odd one and add one; the sequence plotted on a logarithmic scale.

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.

dynamics · Collatz Closed after 3 uses of the universal. The Herbrand expansion of a first-order question at 5 stages, with the number of remaining models at each. It reaches nought after 3 instantiations.

The instance that has to be guessed

Every rule of a propositional tableau replaces a formula by shorter ones, which is why it stops. The rule for a universal claim does not replace it — it keeps it and adds an instance — and one word changing turns a decision procedure into a search that may run forever.

logic · Proof systems

Named alongside it

The objects these essays reach for when they reach for this one.

IterationTerminationCellular automatonCollatzCompletenessComputationDecision procedureGliderHalting problemHeuristicLocalityLogarithm

All concepts