Jong Luo
中文
← Back to the timeline

· Writing · draft

A Gödel trilogy

Three small programs, each showing one fact behind the incompleteness theorem.

Three facts are enough to demonstrate Gödel’s first incompleteness theorem1:

  1. A program can obtain its own source, with no outside help.
  2. A Turing machine can be encoded as a first-order sentence.
  3. 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

  1. The three facts are phrased as in the repos’ READMEs: self-lifter, Python2FOL, lk-proof-machine. ↩

  2. Addition and multiplication are all it takes, which is exactly why arithmetic is strong enough to talk about programs. ↩