Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 37 · Formal Systems and Completeness

Gödel's Incompleteness and Computability

Understand Gödel numbering, the idea behind the incompleteness theorems, the halting problem and Turing's diagonal proof, with runnable Python for encoding and self-reference.

Completeness tells us first-order logic can prove every logically valid statement. A natural next hope, which drove David Hilbert's programme in the 1920s, was bigger: find a finite, consistent set of axioms for all of mathematics from which every true statement can be proved, and an algorithm to decide any statement. In 1931 Kurt Gödel showed the first part is impossible; in 1936 Alonzo Church and Alan Turing showed the second is too. This lesson gives the shape of both results and runs their key tricks.

Gödel numbering: statements about statements

The first insight: formulas and proofs are finite strings, so they can be encoded as natural numbers. A Gödel numbering assigns each symbol a code and each string a number, for example by prime-power coding: the string with codes c₁, c₂, …, cₖ becomes 2^c₁ · 3^c₂ · 5^c₃ ⋯. Unique prime factorization makes decoding possible. Once formulas are numbers, arithmetic can talk about its own formulas and proofs: "n is the code of a proof of the formula with code m" becomes a statement about natural numbers.

Python Gödel numbering with prime powers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first incompleteness theorem

Take a formal system F that is consistent, can express basic arithmetic (like Peano Arithmetic) and has a computable set of axioms (so proofs can be checked by a program). Gödel built, by a diagonal trick like the one in Cantor's argument, a sentence G that says, in effect, "G has no proof in F".

  • If F proved G, then F would prove something false (G says it has no proof), so F would be unsound or inconsistent.
  • If F proved ¬G, then F would claim a proof of G exists; for consistent systems that fails too (under a mild extra assumption, ω-consistency; Rosser removed it).
  • So a consistent F proves neither G nor ¬G. Yet G is true, because it really has no proof.

The second incompleteness theorem: such an F cannot prove its own consistency statement Con(F). This is why ZFC, discussed in the ZFC lesson, cannot certify its own safety.

Incompleteness does not say "some things are unknowable" in a mystical sense. It says that any single fixed, checkable axiom system for arithmetic leaves some arithmetic truths unprovable. You can always add G as a new axiom, but the new system has its own unprovable sentence.

Self-reference: the programming view

The self-referential sentence is cousin to a quine, a program that prints its own source. A quine uses a template string and formats it with its own text, so no infinite regress arises. The same "template applied to its own description" idea builds Gödel's sentence.

Python A quine: self-reference without paradox

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The program prints exactly its own two lines of source.

Computability and the halting problem

Turing asked: is there an algorithm that, given the source of any program P and an input x, decides whether P halts on x? Suppose a function halts(p, x) existed. Define a mischievous program:

Python
def paradox(p):
    if halts(p, p):      # does p halt when run on its own source?
        while True: pass  # then loop forever
    # otherwise halt immediately

Now ask what paradox(paradox) does. If it halts, then halts said so, so it loops forever. If it does not halt, halts said so, so it halts. Contradiction, so halts cannot exist. This is the diagonal argument again: the program list is countable, and paradox differs from every program on its own input. The halting problem is undecidable but semi-decidable: running P and waiting tells you when it does halt, but never that it won't.

Python The diagonal argument applied to a finite list of 'halting oracles'

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In every row the prediction is wrong, which is the whole proof in miniature. (In this toy model paradox simply reports what it would do instead of really looping.)

Consequences

  • Rice's theorem: every nontrivial question about what a program computes (does it ever output 0? is it equivalent to program Q?) is undecidable. Perfect bug finders, virus detectors and optimizers cannot exist; real tools approximate.
  • Church-Turing thesis: anything computable by an effective procedure is computable by a Turing machine; lambda calculus, recursive functions and every modern programming language have equal power.
  • Hilbert's Entscheidungsproblem (decide validity of first-order statements) is undecidable, although valid statements can be enumerated by a complete calculus. Invalid statements may never be refuted by search.
  • Decidable fragments are valuable in practice: propositional logic (SAT), Presburger arithmetic (no multiplication), monadic first-order logic, many theories used by SMT solvers.
flowchart TB
    A["Gödel numbering: formulas are numbers"] --> B["Diagonal lemma: a sentence about itself"]
    B --> C["Incompleteness: unprovable truths"]
    A --> D["Programs are numbers"]
    D --> E["Diagonal program"]
    E --> F["Halting problem undecidable"]

Both great limit results grow from the same two ideas: encode syntax as numbers, then diagonalize.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is a Gödel numbering?

    It lets arithmetic statements refer to formulas and proofs, which makes self-reference possible.
  2. 2. What does the first incompleteness theorem say about a consistent, computably axiomatized system that includes arithmetic?

    Such a system has a sentence G that is true but neither provable nor refutable in it.
  3. 3. Why can no program decide whether any program halts?

    The paradox program halts exactly when the decider says it will not, so no correct decider can exist.
  4. 4. Which statement about the halting problem is true?

    Run the program: if it halts you find out, but if it does not halt you never can be sure.

Summary

  • Gödel numbering turns syntax into arithmetic, so a system can speak about its own proofs.
  • First incompleteness: a consistent, computably axiomatized theory of arithmetic has true but unprovable sentences; second: it cannot prove its own consistency.
  • The halting problem is undecidable by the same diagonal trick; Rice's theorem extends this to all nontrivial semantic properties.
  • Real tools work around these limits with decidable fragments, approximations and human-supplied hints.

Next: DPLL and SAT Solvers