Matpic
mathematics, in pictures
Concept

Turing machine

An idealised computer that reads and writes symbols on an unbounded tape, one cell at a time, under a finite table of rules. The table is indexed by the machine's state and the symbol read, and whatever can be computed at all can be computed by such a machine.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

All 20,736 two-state Turing machines, by when they halt. A bar chart of the two-state, two-symbol Turing machines by halting step on a blank tape: 1: 6912, 2: 2304, 3: 384, 4: 128, 5: 16, 6: 40, never: 10952.

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.

logic · Diagonalisation Every three-state machine and what becomes of it. halt: 1379; no halting entry: 12492; exact repeat: 361; shifted repeat: 2254; dies backwards: 36; unexplained: 27.

The machines that need a reason never to stop

Run every three-state machine on a blank tape and the ones that halt announce themselves: the longest stops after 21 steps. The work is in the others. Each needs a reason it will never stop, and four simple kinds of reason settle all but 27 of them — machines that sweep back and forth over a growing tape and defeat every check that looks for a repeat.

logic · Diagonalisation Four dominoes and a match: the same word along the top and the bottom. Dominoes b/ca, a/ab, ca/a, abc/c; the sequence 2, 1, 3, 2, 4 spells abcaaabc on both rows.

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.

logic · Diagonalisation What all small machines leave on the tape. All 16777216 two-symbol Turing machines with three states, run to step 22: 7571840 halt, leaving 95 distinct strings; most common 0 (2097152), 1 (2097152), 00 (722752); the longest strings are the rarest, up to 20.85 bits.

The shortest description nobody can certify

A string's complexity is the length of the shortest program that prints it. Counting shows almost every string has no short program, and diagonal arguments show nothing can compute the length, or even prove it large for any single string past a fixed point. All 16,777,216 three-state Turing machines leave only 95 strings on their tapes, and a compressor treats π exactly as it treats random bits.

logic · Diagonalisation

Named alongside it

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

Busy beaverExhaustive searchHalting problemUndecidabilityReductionBreadth-first searchComputationComputer-assisted proofCounting argumentDecidabilityDiagonal argumentIncompleteness

All concepts