Kurt Gödel · Vienna · 1931

Gödel's Endgame

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.

Find a sentence the machine can neither print nor print the NOT of.
Gödel (1931), Monatshefte für Mathematik und Physik 38: 173–198. A game built from the paper.
Find a sentence the machine can neither print nor print the NOT of.
Act 1 of 3 · Hilbert's promise

Hilbert's machine
You are the machine now. Which do you print?
Find a sentence the machine can neither print nor print the NOT of.
Act 2 of 3 · Every sentence gets a number

Pack the sentence 1 + 1 = 2 into one number.

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.

1

Unpack this number back into a sentence.

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.

A new kind of sentence. You are the machine: which do you print?

Hilbert's machine
The machine has printed sentence number 11,530,778,490.

Hint: you packed that number a minute ago.

Find a sentence the machine can neither print nor print the NOT of.
Act 3 of 3 · The sentence

Fill the gap so the sentence talks about itself.

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.

Hilbert's machine
Your sentence
It talks about

You are the machine. Which do you print?

Hilbert's machine

In plain words it says: the machine never prints this sentence.

Find a sentence the machine can neither print nor print the NOT of.
Hilbert's repair

“Then I'll teach my machine your sentence.”

Machine II prints everything Machine I prints, and your sentence too. But the recipe works for any machine. Change one word:

Hilbert's machine · II
Machine II can neither print this one nor its NOT, for the same reason as before. Teach it this one, and Machine III has its own. Every repair gets a new sentence.
Read further
  1. Why multiplication. With addition alone a machine can settle every sentence about whole numbers (Presburger, 1929). Multiplication is what lets one number hold a whole list, and so a whole sentence or a whole proof. That is the step that lets arithmetic talk about its own machine.
  2. The filing trick is Gödel's. He gave each sign a number and packed strings of signs as products of prime powers, just as you did. His codes are different (odd numbers for the basic signs), and he then built “is a proof of” out of forty-six definitions, all of them arithmetic.
  3. The gap is Gödel's trick too. In the paper, a formula with a free spot is filled with its own number. “Written twice, the second time in quotes” is the same move in words (the philosopher W. V. Quine's way of saying it).
  4. Honest is more than Gödel needed. He assumed only that the machine never prints a sentence and its NOT together (in a slightly stronger form). Rosser (1936) got by with exactly that.
  5. The last request. The machine can't print “I never print a false sentence” either: if it could, it could follow the argument you just made and print your sentence. That is the paper's last proposition, now called the second incompleteness theorem.
  6. What it does not say. Not that mathematics is broken or that some truths are unknowable. You know your sentence is true. No single fixed machine catches every truth about whole numbers.

How to play

The aim. Hilbert promises his machine prints every sentence about whole numbers or its NOT. Find a sentence where it can do neither.

Act 1: play the machine

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.

Act 2: sentences become numbers

Pack a sentence into one number by multiplying primes, then unpack a number by dividing. Then judge a sentence about the machine itself.

Act 3: the sentence

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.

About this game

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.

What the paper does

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.

How the game tells it

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

The mechanism

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.