Diagonalisation — the series

1. 

   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. 

   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 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. 

   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. 

   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. 

   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
7. 

   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.

   part 7 · logic
8. 

   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.

   part 8 · logic
9. 

   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.

   part 9 · logic

All series