The Berry paradox is a self-referential puzzle about descriptions: it seems to define a number while simultaneously denying that the number can be defined that briefly. Gregory Chaitin’s major contribution was to turn its informal contradiction into a rigorous theorem of algorithmic information theory—a proof of mathematical incompleteness based on program-size complexity.
The paradox
Consider:
“The smallest positive integer not definable in under sixty letters.”
There are only finitely many English phrases under sixty letters, so only finitely many integers can be defined by them; therefore some positive integer must be undefinable in under sixty letters. Since every nonempty set of positive integers has a least member, there must be a smallest such integer. But the quoted phrase itself has fewer than sixty letters, so it defines that very integer in under sixty letters—contradiction.
The core defect is the unformalized word “definable.” In ordinary language, it permits a vicious circle: a phrase can refer to the totality of brief definitions while itself being one of those brief definitions.
Chaitin’s formalization
Chaitin replaced vague “definition in words” with Kolmogorov complexity: the length, in bits, of the shortest program that outputs a given string or integer and then halts. This makes “description length” precise, provided a fixed universal machine or programming language is chosen.
The Berry-style expression becomes, roughly:
“The first string whose Kolmogorov complexity exceeds n.”
In a formal system T, suppose T could prove statements of the form K(x) > n for arbitrarily large n. Then a short program could search through T’s proofs, find the first provable example of complexity greater than n, and output it. That program’s length is only about log n plus a fixed overhead—far below n for large n—so it would produce an object whose complexity is provably greater than its own description length. That is the formal Berry contradiction.
Chaitin’s incompleteness theorem
The contradiction is avoided because sufficiently strong, consistent formal systems cannot prove that any particular string has complexity above a certain threshold.
More exactly: for every consistent formal system T rich enough to formalize computation, there is a constant LT such that T proves no theorem of the form:
K(x) > LT
Yet there are infinitely many strings with complexity greater than LT; the system simply cannot certify any of them.
So Chaitin’s theorem says, informally:
A formal system of information content N cannot establish that a specific object has algorithmic complexity substantially greater than N.
Why it matters
| Topic | Gödel’s route | Chaitin’s route |
|---|---|---|
| Informal source | Liar paradox: “This statement is unprovable.” | Berry paradox: “The smallest number not briefly definable.” |
| Formal tool | Self-reference and Gödel numbering | Kolmogorov complexity and program size |
| Result | In any sufficiently strong consistent theory, some true arithmetical statements are unprovable | Such a theory cannot prove lower bounds on the complexity of specific strings beyond a fixed bound |
| Philosophical upshot | Limits of formal proof | Limits on extracting compressive, provable information from axioms |
Chaitin’s result is therefore not merely a curiosity: it gives an information-theoretic reading of incompleteness. A finite axiom system contains finite information, and it cannot certify the randomness—or, equivalently, the high algorithmic complexity—of individual objects beyond that finite information content.
Relation to Ω
Chaitin also connected this line of thought to his constant Ω, defined as the probability that a randomly generated program for a fixed universal machine eventually halts:
Ω = ∑p halts 2−|p|
The bits of Ω encode, in a strong sense, the solution to the halting problem; knowing sufficiently many initial bits would let one resolve corresponding halting questions. Consequently, the bits of Ω are algorithmically random, and no sufficiently strong consistent theory can prove more than finitely many scattered bits of it.
Historical note
Russell published the paradox and attributed it to G. G. Berry, an Oxford librarian. Chaitin later noted that Berry’s original letter concerned not the familiar “smallest integer” formulation but “the first ordinal that cannot be named in a finite number of words”—which appears contradictory because Cantorian set theory implies such an ordinal exists, while the phrase appears to name it finitely.
In short: Berry exposes an informal contradiction in self-referential description; Chaitin converts it into a precise limit on what formal axioms can prove about algorithmic randomness.
No comments:
Post a Comment