Skip to content

Kolmogorov Complexity

Abstract

How much information is in a string of symbols? Claude Shannon answered for a source that emits symbols with known probabilities. Kolmogorov complexity answers for a single object, with no probabilities at all: the information content of a string is the length of the shortest program that prints it. A million digits of a simple pattern are cheap; a million truly random digits cost their full length, because nothing shorter than “print this exact sequence” produces them. The idea was discovered three times over between 1960 and the late 1960s, gives the sharpest available definition of what “random” means, and turns out to be uncomputable, yielding a fresh proof of Gödel’s incompleteness as a side effect.

Three Independent Discoveries

The measure now called Kolmogorov complexity was found by three people who were not in contact, which is why it is sometimes written with all their names. Ray Solomonoff, an American working on machine inference, got there first, publishing the foundational idea of algorithmic probability in 1960 and 1964 as part of a theory of prediction. Andrey Kolmogorov, the towering Soviet probabilist, published the same core theorem independently in 1963 and 1965, coming at it from the question of what randomness fundamentally is. And Gregory Chaitin, born in Chicago in 1947, worked it out as a teenager at the Bronx High School of Science and City College, publishing in the late 1960s. When Kolmogorov later learned of Solomonoff’s priority he acknowledged it; the field nonetheless attached itself to the most famous name. Chaitin went on to a long career at IBM’s Watson Research Center, building the subject he calls algorithmic information theory.

The definition is disarmingly simple. Fix a universal programming language. The complexity K(x) of a string x is the length of the shortest program in that language whose output is x. The string “01” repeated a thousand times has low complexity: a short loop prints it. A string of a thousand coin-flip outcomes has high complexity, close to its own length, because no program describes it more briefly than by quoting it in full. Complexity measures incompressibility, and compressibility is the presence of a pattern. This is the theoretical bedrock under practical data compression: a compressor is a bet that its input has low Kolmogorov complexity, and files that genuinely do not compress are the ones with no exploitable structure.

Why the Choice of Language Does Not Matter

An obvious objection is that the answer depends on the language, and a string cheap in one might be expensive in another. The invariance theorem disposes of this. Any two universal languages can simulate each other with a fixed translator, so their complexity values for the same string differ by at most a constant that does not depend on the string. For long strings this constant washes out, and K(x) is well-defined up to that additive slack. Kolmogorov complexity is therefore an intrinsic property of the object, not an artifact of how you chose to describe it, which is what let it become a foundational notion rather than a programming curiosity.

A Definition of Randomness, and a New Gödel

The payoff Kolmogorov wanted was a rigorous definition of a random object. Intuitively, a random string is one with no pattern, and now that has teeth: a string is Kolmogorov random if its complexity is roughly equal to its length, meaning it cannot be compressed at all. This finally distinguishes the two sequences that classical probability treats identically. A fair coin is equally likely to produce a thousand heads or any specific mixed sequence, yet we feel the all-heads run is not random. Kolmogorov complexity explains the feeling: the all-heads sequence has a short description and the typical mixed one does not.

Then comes the sting. K(x) is uncomputable: no program can take a string and output its Kolmogorov complexity, because doing so would let you solve the halting problem. You can never be sure you have found the shortest program, since a shorter one might still be running, undetectably. Chaitin drew from this a proof of Gödel’s incompleteness theorem that is arguably more intuitive than the original: any consistent formal system with finite axioms has a fixed complexity bound L, and the system can never prove that any specific string has complexity greater than L, even though almost all strings do. Mathematics cannot certify the randomness of the overwhelming majority of random objects, because the proof would be a compression the objects do not permit. Chaitin sharpened this into his constant Ω, defined in 1975, the probability that a random program halts: a perfectly definite real number, every one of whose bits is an unprovable mathematical fact. Ω is the density of the halting problem distilled into a single number that no theory can compute and no proof can pin down, and it is where the theory of information, the theory of randomness, and the limits of proof turn out to be the same subject.

📚 Sources