Kolmogorov Complexity: The Shortest Possible Description of Anything

Take two strings of a million characters each. The first is "01" repeated 500,000 times. The second is the output of flipping a coin a million times and writing down heads as 1 and tails as 0. Both strings are exactly the same length. By any naive measure — character count, file size, entropy of the alphabet used — they look identical. But one of them is simple and the other is about as complicated as a string can be. The question of why, and how to make that difference mathematically precise, turns out to touch the halting problem, the limits of compression, and the outer edge of what mathematics itself can prove.

That's the subject of Kolmogorov complexity: a way of measuring the complexity of a piece of information not by its length, but by the length of the shortest set of instructions that could produce it.

The Concept

Here's the core idea, stated plainly: the Kolmogorov complexity of a string is the length of the shortest computer program that outputs that string and then stops.

The repeating string "01010101..." has low complexity, because you can write a tiny program: "print '01' five hundred thousand times." That program is dramatically shorter than the string itself. The coin-flip string, on the other hand, has essentially no shortcut. If the bits really are random, the shortest program that produces that exact sequence is, more or less, "print 0110100111...[the whole string]." You can't compress it, because there's no pattern to exploit — the description is about as long as the thing being described. A string like this is called algorithmically random or incompressible.

That single idea reframes what "randomness" and "complexity" even mean. Instead of defining randomness through probability (a coin is random if each flip is 50/50), Kolmogorov complexity defines it through description length: a string is random if nothing shorter than the string itself can generate it. A sequence can come from a genuinely random physical process and still, by sheer chance, turn out to be compressible (a fair coin really can produce a thousand heads in a row). Kolmogorov complexity doesn't ask how the string was generated — it asks how hard the string is to describe, after the fact.

This idea was arrived at independently by three people in the early 1960s, which is usually a sign that an idea's time has come. Ray Solomonoff, an American researcher working on machine learning and inductive inference, described the core concept in a 1960 report and a more complete 1964 paper, as a byproduct of building a theory of prediction. Andrey Kolmogorov, one of the most influential mathematicians of the 20th century (he had already built the modern axiomatic foundations of probability theory decades earlier), independently proposed the same measure in 1965 as a way to define the information content of an individual object, rather than relying on probability distributions over whole ensembles of objects. And Gregory Chaitin — at the time a teenager attending the Bronx High School of Science and then City College of New York — independently arrived at essentially the same formulation, publishing "On the Length of Programs for Computing Binary Sequences" in the Journal of the ACM in 1966. When Kolmogorov later learned of Solomonoff's earlier work, he explicitly acknowledged Solomonoff's priority. Because all three contributed essential pieces, the field is usually called Kolmogorov complexity or algorithmic information theory, and the object itself is sometimes written as the Solomonoff–Kolmogorov–Chaitin complexity.

One technical wrinkle makes the whole thing work: complexity depends, in principle, on which programming language or machine you use to measure it. But there's a result called the invariance theorem, proved around the same time by Solomonoff, Kolmogorov, and Chaitin, which shows that the complexity measured on any two "universal" computing systems (anything as powerful as a general-purpose computer) differs by at most a fixed constant, no matter how long the string is. In other words, it doesn't matter whether you measure complexity in Python, C, or some abstract Turing machine — for long enough strings, the answer is essentially language-independent. That's what makes Kolmogorov complexity a property of the string, not of the tool used to measure it.

Why It Matters

The most direct real-world shadow of Kolmogorov complexity is data compression. Every time a ZIP file, an MP3, or a JPEG shrinks a file, it's exploiting the same underlying principle: find a shorter description that regenerates the original. Kolmogorov complexity is the theoretical floor beneath all of this — the absolute shortest possible description of a given piece of data, which no compression algorithm can beat, even in principle. Real compressors like gzip or LZ77 don't compute the true Kolmogorov complexity (they can't — more on that below), but they do provide a computable upper bound on it. If gzip shrinks a file to 10% of its size, you now know that file's true complexity is at most 10% of its original size, even though you can't know the exact minimum.

That upper-bound trick turns out to be scientifically useful in an almost magical way. In 2002, three Italian physicists — Dario Benedetto, Emanuele Caglioti, and Vittorio Loreto — published a paper in Physical Review Letters called "Language Trees and Zipping." Their method: take text in many different languages, measure how well a compressor like gzip can compress one language's text using another language's text as a "dictionary," and use the resulting compression distances to build a family tree of languages — with no linguistic knowledge programmed in at all, no grammar rules, no dictionaries, nothing but raw compression statistics. The tree it produced correctly grouped Romance, Celtic, Germanic, Slavic, Baltic, and Ugro-Finnic language families, and correctly flagged outliers like Maltese and Basque as linguistic isolates. The same compression-distance idea (formalized as "normalized compression distance") has since been applied to cluster genomes by similarity, detect plagiarism, and attribute disputed authorship of texts — all by treating "how much shorter can file B get if you already know file A" as a stand-in for "how similar are A and B," without needing to understand either one.

Kolmogorov complexity also underwrites a rule of thumb used throughout statistics and machine learning called the Minimum Description Length principle, formalized by Jorma Rissanen in the late 1970s: among competing explanations for a dataset, prefer the one that lets you describe the data most compactly, counting both the complexity of the model and the complexity of the data given that model. This is essentially a mathematically rigorous version of Occam's razor — simpler explanations are better, where "simpler" is given a precise, information-theoretic meaning rather than a vague aesthetic one.

Cryptography depends on the flip side of the same coin. A secure encryption key has to be effectively incompressible — unpredictable, patternless, close to algorithmically random — because the moment a key has exploitable structure (a repeating pattern, a predictable relationship between bits), an attacker can describe it more briefly than its raw length, and a shorter description is the first step toward guessing it.

The Details

Here's the catch that makes Kolmogorov complexity more than just a cute definition: it is, in general, impossible to compute. There is no algorithm that takes an arbitrary string as input and reliably outputs its exact Kolmogorov complexity. The reason traces straight back to Alan Turing's halting problem. To know the shortest program that produces a given string, you'd need to examine all shorter candidate programs and determine which ones, when run, actually halt and output that exact string — and determining in general whether a program halts is precisely the problem Turing proved undecidable in 1936. Kolmogorov complexity inherits that undecidability directly.

Chaitin pushed this incomputability to its most extreme and philosophically unsettling form with what's now called Chaitin's constant, or Omega (Ω) — a real number defined as, roughly, the probability that a randomly chosen computer program will eventually halt. Omega turns out to be not just hard to compute but maximally incompressible: every digit of it is algorithmically random, meaning there's no shortcut formula for generating its digits beyond listing them one by one. Chaitin went further and proved an incompleteness result in the spirit of Kurt Gödel's famous theorems: for any specific, consistent axiomatic system for arithmetic, there's some point N such that no digit of Omega beyond that point can ever be proven, within that system, to be a 0 or a 1. It isn't that we haven't yet found the proof — provably, no proof exists inside that system. Chaitin drew a striking philosophical conclusion from this: that there are mathematical facts which are true "for no reason," not derivable from anything simpler, true essentially by accident — an idea that unsettled a field that had spent a century assuming every true statement had, somewhere, a reason.

It's worth sitting with how strange this is. We've known since Gödel that some true statements can't be proven within a given formal system. Chaitin's work shows that this isn't a rare, exotic edge case cooked up to make a point — an infinite number of true facts about Omega's digits are like this, scattered throughout ordinary arithmetic, each one true for reasons that cannot be compressed into any proof shorter than simply stating the fact itself.

Takeaways

Kolmogorov complexity measures the complexity of a specific string as the length of the shortest program that can produce it — not by probability, but by compressibility.
It was discovered independently by Ray Solomonoff, Andrey Kolmogorov, and a teenage Gregory Chaitin in the early-to-mid 1960s, and the invariance theorem guarantees the measure barely depends on which computer or language you use to compute it.
The measure is formally incomputable — no algorithm can determine the exact shortest description of an arbitrary string, a direct consequence of the halting problem.
Real compression tools like gzip provide computable upper bounds on true complexity, and that trick alone has been used to reconstruct language family trees, cluster genomes, and detect plagiarism — all without understanding the content being compressed.
Chaitin's Omega number shows the idea has teeth beyond computer science: it proves that some true mathematical facts have no proof shorter than simply stating them, true "for no reason" in any system of axioms.

Resources: - Li, M. & Vitányi, P. — An Introduction to Kolmogorov Complexity and Its Applications (the standard textbook) - Benedetto, Caglioti & Loreto, "Language Trees and Zipping," Physical Review Letters 88, 048702 (2002) - Chaitin, G. — Conversations with a Mathematician: Math, Art, Science and the Limits of Reason