Matpic
mathematics, in pictures
Series

Diagonalisation — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. The diagonal, and the row built to be off the list. A table of rows of ones and zeros with the diagonal marked, and beneath it the row obtained by flipping every diagonal entry.

    The row that is not on the list

    Write down a list of infinite sequences, any list at all, and there is a rule that builds a sequence missing from it. The rule reads one entry from each row, and it is the single most reused argument in this field.

    part 1 · logic
  2. Does this set contain that one — and the row that is missing. A membership table with the diagonal marked, and beneath it the complement of the diagonal, which is not among the rows.

    A list that cannot contain itself

    The set of all sets that do not contain themselves is not a set. The argument is the diagonal again, applied to a table whose rows and columns are the same objects, and it destroyed the foundations of mathematics in a postcard.

    part 2 · logic
  3. The diagonal, and the row built to be off the list. A table of rows of ones and zeros with the diagonal marked, and beneath it the row obtained by flipping every diagonal entry.

    The sentence that says it has no proof

    Number every sentence and every proof, and a formal system can talk about itself. Then the diagonal is available one more time, and what it builds is a sentence that is true exactly when it is unprovable.

    part 3 · logic
  4. Adjectives that describe themselves, and the one that cannot exist. A grid of 8 adjectives against the same adjectives as written words, marked where the property holds of the spelling; the diagonal marks self-describing adjectives, and a flipped diagonal row labelled heterological matches no row.

    The word that cannot describe itself

    Some adjectives describe themselves — 'short' is short — and some do not — 'lengthy' is not lengthy. Call the second kind heterological, and ask whether 'heterological' is heterological. It is exactly when it is not. The diagonal that beat every list of numbers, every set of sets and every provability predicate has been turned on words that describe words, and it proves that no language can contain a word for its own notion of describing, naming or truth.

    part 4 · logic
  5. A program whose output is its own text. The 32-character program (f=>f(f))(f=>"(f=>f(f))("+f+")") beside its output, which is identical.

    The program that prints itself

    The diagonal argument has always been used to destroy — to show that a list misses something, that a sentence cannot be proved. Run the same move the other way and it builds. Kleene's recursion theorem says every program can be given its own text to work with, and the proof is a program that prints itself, thirty-two characters long, which can be run and checked.

    part 5 · logic
  6. 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.

    part 6 · logic

All series