David Hilbert has a machine for sentences about whole numbers, like 2 × 3 = 6. It is honest: it never prints a false sentence. And Hilbert makes a promise:
“Give my machine any sentence. It will print it, or print its NOT. Always.”
You will play the machine, learn how a sentence becomes a number, and then write one sentence of your own.
Every symbol has a code. Tap the symbols in order. Each tap multiplies the number by the next prime (2, 3, 5, 7, 11) raised to the symbol's code.
Divide by 2 as often as it goes, then by 3, then by 5. How many times each prime goes in is the code of a symbol.
Hint: you packed that number a minute ago.
Hilbert: “Write one my machine can't settle.” Here is a sentence with a gap. Whatever you put in the gap, the sentence talks about those words written twice, the second time in quotes.
In plain words it says: the machine never prints this sentence.
Machine II prints everything Machine I prints, and your sentence too. But the recipe works for any machine. Change one word:
The aim. Hilbert promises his machine prints every sentence about whole numbers or its NOT. Find a sentence where it can do neither.
Write a sentence with the keypad (or tap Give me one) and hand it to the machine. First it checks it is a sentence at all: xyz or 2 + = 4 are not. Then you decide, as the machine: Print it if it is true, Print its NOT if it is false. The machine never prints a false sentence.
Pack a sentence into one number by multiplying primes, then unpack a number by dividing. Then judge a sentence about the machine itself.
Choose what goes in the gap. The two lines under the machine show your sentence and what it talks about; when they are the same, it talks about itself. Then try to print it.
The paper. Kurt Gödel, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”, Monatshefte für Mathematik und Physik 38 (1931): 173–198. DOI 10.1007/BF01700692. Built from B. Meltzer's English translation (1962). Game built from this paper; the paper is the authority where the two disagree.
Hilbert hoped for a fixed rulebook for whole numbers that settles every question about them: proves each sentence or its opposite. Gödel showed it cannot be done. First he gives every sign a number and packs strings of signs into single numbers with prime powers, so that “this is a proof of that” becomes a fact about numbers, which the rulebook can state. Then he fills a sentence's gap with the sentence's own number and gets a sentence that says of itself that it cannot be proved. If the rulebook never contradicts itself, it proves neither that sentence nor its opposite, and the sentence is true. A bigger rulebook has its own such sentence. And the rulebook cannot prove that it never contradicts itself.
The rulebook is a machine, and “proves” is “prints”. Act 1 plays Hilbert's promise on sentences with + and ×. Act 2 plays the paper's packing of strings into numbers, with small codes of our own (the paper's are odd numbers for its basic signs) so that the numbers stay readable. Act 3 tells the self-referring sentence in words: “written twice, the second time in quotes” is the philosopher W. V. Quine's way of saying Gödel's filling of a gap with its own number. The machine is assumed honest, which is more than Gödel assumed (see Read further on the end screen).
A toy. The game runs a small model built to illustrate the argument, not the paper's formal system.
Type: Josefin Sans (Santiago Orozco) and Courier Prime (Alan Dague-Greene), both under the SIL Open Font License.