Three facts are enough to demonstrate Gödel’s first incompleteness theorem1:
- A program can obtain its own source, with no outside help.
- A Turing machine can be encoded as a first-order sentence.
- Proofs in first-order logic can be searched for; proofs are recognizable.
In spring 2023 I wrote one small program for each.
I · self-lifter
It rewrites any script you give it into a new script that can print its own source. Below is the shortest kind: a JavaScript expression that returns itself. Run it and check that the output matches the source exactly.
(function q(){return '('+q+')()'})()II · Python2FOL
Compiles a Python program into a first-order sentence that uses only addition and multiplication2. The sentence is true if and only if the program halts.
III · lk-proof-machine
Searches for first-order proofs using Gentzen’s sequent calculus (LK). If a proof exists, it will eventually find it.
Put the three together and you get the classic self-referential argument: a program reads its own source, writes “I do not halt” as a sentence about arithmetic, and goes looking for a proof of it.
Footnotes
-
The three facts are phrased as in the repos’ READMEs: self-lifter, Python2FOL, lk-proof-machine. ↩
-
Addition and multiplication are all it takes, which is exactly why arithmetic is strong enough to talk about programs. ↩