Have identical logical skeleton involving self referential contradictions
Are instances of Cantor's Diagonal Argument
Given any proposed complete system or decision procedure, you can explicitly exhibit what it misses
Are unfixable.
1.
2.
3.
4.
-
Gödel: add GG as a new axiom to get system F′F′. Now F′F′ has its own Gödel sentence G′G′ that it can't prove. You can iterate this through the transfinite and never reach completeness.
-
Turing: suppose you add an oracle for the halting problem, giving you machines that can consult a "halt/not-halt" black box. Now this generates the Turing jump hierarchy: ∅<∅'<∅′′<⋯
-
Gödel: given formal system F, you can construct a true sentence GF that F cannot prove.
-
Turing: given any proposed halting decider H, you can construct a specific program-input pair on which H gives the wrong answer.
The Fixed Point Theorem
-
Gödel's incompleteness follows from the Diagonal Lemma. (also called Gödel's fixed-point theorem): for any formula φ(x), there exists a sentence ψ such that F ⊢ψ ↔ φ(⌜ψ⌝).
-
The undecidability of halting follows from Kleene's recursion theorem (the second recursion theorem): for any computable transformation ff, there exists an index ee such that φe=φf(e). These programs can effectively "know" their own index.
Lawvere's Fixed point Theorem 1969
Structurally parallel.
see
