Algorithmic information and the limits of compression

Context

Three inventors, one idea. In the early 1960s the same definition occurred independently to three people: Ray Solomonoff (1960, a Chicago-trained loner working on machine inference), Andrei Kolmogorov (1965, the towering Soviet mathematician who had already axiomatized probability itself), and Gregory Chaitin (1966, a teenager in New York who submitted his paper while still a student at City College). The definition: the information content of a string is the length of the shortest program that produces it. Shannon had defined information through probability distributions; this defines it for a single object, through computation. A million digits of π contain a few lines of information; a million random coin flips contain a million bits, because no shorter description exists. Randomness is incompressibility — the first principled definition randomness ever had.

The catch is the point. Kolmogorov complexity is uncomputable: no algorithm can, in general, find the shortest program for a string, or even certify that a string is random. Chaitin's proof is the Berry paradox made rigorous — "the smallest number not describable in under twenty words" describes it in ten — and it welds algorithmic information directly to Gödel and Turing: a formal system of complexity N can never prove that any specific string has complexity much greater than N. There are at most finitely many provable statements about randomness, ever, in any system. Chaitin's Ω — the halting probability, a perfectly well-defined real number whose digits are provably unknowable — is undecidability distilled into a single number.

Where it sits. This is the unit where the Information path fuses with the limits of computation: compression, prediction, and proof turn out to be the same activity seen from three angles, and all three hit the same wall. It also quietly underwrites machine learning — Solomonoff's induction is the idealized theory of learning from data, and "find the shortest description" is the oldest formulation of Occam's razor that actually has theorems.

How to read it

Anchor. Moore & Mertens, The Nature of Computation, chapter 7 ("The grand unified theory of computation") and the Kolmogorov-complexity sections. The real textbook treatment. ~10 hours.

Companion. Gregory Chaitin, Meta Math! or his essays on algorithmic information. Chaitin is an eccentric writer, but the enthusiasm is infectious and the ideas are genuinely his.

Sit with Ω until it bothers you: a perfectly well-defined real number that no algorithm can compute — and why that is Gödel and Turing wearing information-theory clothes.