Quantitative incompleteness — Chaitin's information bound

Parent: relaxing-undecidability

Gödel says some truth is unprovable. Chaitin grades incompleteness in bits: a theory can't prove any object is much more random than the theory itself.

Chaitin's incompleteness

Let K(x) be the Kolmogorov complexity (shortest program producing x). For a consistent, sound, recursively-axiomatized theory T whose axioms have program-size complexity c, there is a constant such that T proves "K(x) > n" for only finitely many n — essentially only up to n ≈ c + O(1).

So a formal system of c bits of information cannot certify randomness beyond c. Incompleteness becomes a conservation law: provable complexity is bounded by the axioms' information content. ([[probabilistic-undecidability|Ω]] is the extreme case — an infinite stream of theorems each needing its own axiom.)

Tie — this is requisite variety for proof. Just as a regulator needs variety ≥ the disturbance it absorbs, a proof system needs information ≥ the complexity of what it certifies. You can't verify a system more complex than your certificate language — the verification-bandwidth ceiling (relaxing-undecidability, certificates) is Chaitin's bound in disguise.