Kolmogorov Complexity

The size of the shortest program that prints a string turns out to be its truest measure of information — and, on any interesting string, forever out of reach.

Look at these two strings of a hundred characters each:

A: ababababababababababababababababababababababababababababababababababababababababababababababababababab

B: hqk3nzp8x7t2wjr0f5cvbg1ml9dsyoue4ai6q0zknvxpwr7hjl2m5tbcf8gd3sya9qeu1oivpwr4kzxjm0nybhcglt6sd8fape25

Both have length 100. Both, on a naive counting of ink and pixels, contain “the same amount” of stuff. But something feels obviously different. A is trivial — you can describe it in seven words: the pair “ab” repeated fifty times. B, if you had to send it to a friend, would take a hundred characters — there is no shorter way to say it. That intuition — that some strings are compressible and some aren't, and that the incompressible ones are somehow the “real” random ones — is what Andrey Kolmogorov, Ray Solomonoff, and Gregory Chaitin turned into mathematics in the mid-1960s.

The definition

Fix a universal Turing machine U — a laptop, essentially. The Kolmogorov complexity of a string s, written K(s), is the length of the shortest program that, when run on U, prints s and halts.

The choice of U feels arbitrary, and it is — if you switch to a different universal machine U′, complexities shift, but only by a constant. That constant is the length of an interpreter that lets one machine emulate the other. Because it doesn't depend on s, it washes out for long strings. This is the invariance theorem, and it is the reason K deserves to be called an intrinsic measure at all.

String A above has small K: a few dozen bits of Python (print("ab" * 50)) suffices. String B, being random-looking, almost certainly has no shorter description than itself — roughly 100 characters' worth. That gap is the whole story.

Randomness as incompressibility

This gives us the first precise, satisfying definition of randomness. A string of length n is Kolmogorov random if K(s) is roughly n — if there is no program appreciably shorter than the string itself that produces it. Randomness is not a property of the process that generated the string; it is a property of the string. A random string is one that cannot be compressed.

Two beautiful facts fall out immediately.

The first is a counting argument. There are 2ⁿ binary strings of length n, but only 2ⁿ − 1 shorter programs to describe them with. So almost every string is incompressible — most strings are random. Randomness is the rule, not the exception. And yet the strings we notice in daily life — laws of physics, English sentences, images of a face — are wildly compressible. That is why we notice them.

A random string is not one produced by a random process. It is one that has no shorter description than itself.

The second is that K distinguishes structure from noise in a way that compression algorithms only approximate. A gzip'd file is a lower bound on K: since gzip is a specific short program, K(s) is at most the size of the gzip output plus a small constant. Every compression tool you use — ZIP, JPEG, MP3, an LLM predicting the next token — is a heuristic hunt for a short program that reproduces the data. Kolmogorov complexity is the ideal they all approximate.

The uncomputability wall

Here comes the twist. K(s) is not computable. There is no algorithm that, given any string, tells you its Kolmogorov complexity. This isn't a matter of the algorithm being slow. It provably cannot exist.

The proof is a self-referential trap in the spirit of Russell and Gödel. Suppose you had a program K_of that, given a string, returned its complexity. Then, for any number n, you could write a short program: “search through strings in order and print the first string s for which K_of(s) > n.” This program has some fixed length — say, a few hundred bits — plus the bits needed to encode n, which grows only as log n. So the total program is much shorter than n once n is large. But it prints a string whose Kolmogorov complexity is, by definition, greater than n. Contradiction. The program cannot exist.

So we are in a strange position. Kolmogorov complexity is the “correct” measure of the information content of a string — well-defined, machine-independent up to a constant, giving a clean definition of randomness — and it is also, for any particular string, something we can never fully know. We can produce upper bounds (by exhibiting short programs) but never confirm we have found the shortest. Somewhere in the tail, a cleverer description might always be lurking.

What it changed

Kolmogorov complexity reframes several problems that had felt separate. Randomness stops being about probability distributions and becomes about description length. Occam's razor — prefer the simpler explanation — gets a precise formalization: prefer the hypothesis with the shortest program that predicts the data. This is the foundation of Solomonoff induction, a mathematically ideal (and, of course, uncomputable) form of Bayesian reasoning. It underlies the minimum description length principle in statistics, the theoretical justification for many machine-learning regularizers, and it gives a language for asking why some laws of physics feel “deep” and others “ad hoc.” A deep law is one with low K that explains data of high K.

The uncomputability is not a bug; it is where the theory becomes philosophy. It says that some truths about finite objects — the complexity of this specific string — are permanently beyond mechanical proof. Not because the string is large, but because the question is self-referential in a way that no algorithm can escape. Gödel's shadow, cast onto the theory of information.

What survives is the picture. Every string sits somewhere between full pattern (small K) and full noise (K near its length). Compression, learning, science, and understanding are all the same activity, from this angle: the search for a short program that outputs the world.