Gödel, Turing & Information
Chaitin’s information-theoretic proof of Gödel’s incompleteness theorems. The halting problem implies the uncomputability of \(K(x)\), and Omega — the halting probability — is a maximally random, unknowable number.
12.1 Gödel’s Incompleteness as an Information Statement
Gödel’s first incompleteness theorem (1931) states that any sufficiently powerful consistent formal system \(F\) contains statements that are true but unprovable within \(F\). Chaitin recast this in information-theoretic terms using Kolmogorov complexity.
Chaitin’s incompleteness theorem:For any consistent formal system \(F\) with a computable set of axioms, there exists a constant \(c_F\) such that \(F\) cannot prove the statement “\(K(x) > c_F\)” for any specific string \(x\), even though \(K(x) > c_F\) is true for almost all strings.
Proof idea: If \(F\) could prove\(K(x) > c_F\) for some \(x\), we could write a program that searches through all proofs of \(F\) until it finds one asserting\(K(y) > c_F\) for some \(y\), then outputs that \(y\). This program has length \(O(\log c_F)\) bits (to encode \(F\)and \(c_F\)). For large enough \(c_F\), this program is shorter than \(c_F\) — contradicting \(K(y) > c_F\).
The constant \(c_F\) measures the “information content” of the axiom system \(F\). More powerful systems have larger \(c_F\)— they can certify more strings as complex — but there is always a complexity threshold beyond which the system is blind.
12.2 The Halting Problem Implies \(K\) is Uncomputable
Turing’s halting problem (1936): there is no algorithm that, given a program \(p\)and input \(w\), correctly decides whether \(p(w)\) halts. This directly implies the uncomputability of \(K\):
Step 1: Assume K is computable
Suppose algorithm \(A\) computes \(K(x)\) for all \(x\).
Step 2: Construct a halting oracle
Given \(p\), enumerate all strings \(x\) and test \(K(x) > |p| + c\)using \(A\). If \(K(x) > |p| + c\) then \(p\) cannot compute \(x\) — this solves the halting problem. Contradiction.
Conclusion
Since the halting problem is undecidable (Turing 1936), \(K\) is uncomputable. \(\square\)
12.3 Chaitin’s \(\Omega\): The Halting Probability
Fix a universal prefix-free Turing machine \(U\). The halting probability is:
\[ \Omega = \sum_{\substack{p \in \{0,1\}^* \\ U(p)\;\downarrow}} 2^{-|p|} \]
where \(U(p)\downarrow\) means \(U\) halts on program \(p\).
\(\Omega\) is a well-defined real number in \([0,1]\) (the Kraft sum over prefix-free programs is at most 1). Its properties are astounding:
- 1.Maximally random: The binary digits of\(\Omega\) form a Martin-Löf random sequence. No regularity can be found — every effective statistical test passes. \(K(\Omega_{1:n}) \ge n - O(1)\).
- 2.Computable enumerable but not computable:We can compute \(\Omega\) from below (by running more and more programs and adding \(2^{-|p|}\) for each halting one), but we can never determine a specific digit with certainty.
- 3.Encodes all math: Knowing the first \(n\)bits of \(\Omega\) would allow one to decide all mathematical questions expressible in at most \(n\) bits — including every open conjecture (Riemann hypothesis, Goldbach, etc.) up to that complexity.
- 4.Machine-dependent but equally random:Different universal machines give different \(\Omega\) values, but all are equally maximally random — they differ in finitely many bits.
12.4 The Berry Paradox
The Berry paradox (G.G. Berry, ~1906) is a self-referential paradox in natural language:
“The smallest positive integer not definable in fewer than thirteen words.”
This phrase is itself fewer than thirteen words, yet it purports to define a number that requires at least thirteen words to define — a contradiction. The paradox arises because “definable” cannot be formally captured within the system.
Chaitin formalized this as the proof of uncomputability of \(K\): “the first string \(x\) with \(K(x) > n\)” is a description of length \(O(\log n)\) bits — shorter than \(n\)for large \(n\) — but the string it names has complexity greater than \(n\). Formal contradiction. The resolution: no formal system can prove statements of the form\(K(x) > c_F\) beyond its own information content \(c_F\).
12.5 The Computability Hierarchy
Information-theoretic complexity stratifies the landscape of sets and problems:
12.6 Philosophical Implications
Limits of Formal Mathematics
Gödel showed that any consistent formal system powerful enough to describe arithmetic has true but unprovable statements. Chaitin’s version quantifies this: a system with\(n\) bits of axioms can only “see” complexity up to roughly\(n\) bits. Mathematics itself is information-limited.
Randomness in Pure Mathematics
\(\Omega\) demonstrates that mathematical truth can be irreducibly random. The digits of \(\Omega\) satisfy no pattern, no formula, no rule — yet each digit is a perfectly definite mathematical fact (whether a specific program halts). Random truth exists.
Epistemological Limits
The uncomputability of \(K\) means we can never fully characterize the complexity of nature. Compression is the best we can do. Science, in this view, is the search for short descriptions of observed data — an approximation to Kolmogorov complexity.
Algorithmic Probability & Solomonoff Induction
Solomonoff defined the algorithmic probability \(m(x) = \sum_{p: U(p)=x^*} 2^{-|p|}\)as the ultimate prior over all computable hypotheses. Bayes’ rule with this prior gives optimal inductive inference — also uncomputable, but the theoretical ideal against which all learning algorithms are measured.
Historical Timeline
Further Reading
- An Introduction to Kolmogorov Complexity and Its Applications — Li & Vitányi (3rd ed., 2008). The definitive textbook.
- Algorithmic Information Theory — G.J. Chaitin (1987, free online). Primary source for Omega.
- The Unknowable — G.J. Chaitin (1999). Accessible account for general readers.
- Gödel, Escher, Bach — Douglas Hofstadter (1979). Self-reference, strange loops, and incompleteness.
- Turing’s original paper — “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936).