Consider the number 10100. It is enormous — a one followed by a hundred zeros. Writing it out in full would take 101 digits. But I just described it in five characters. That gap between the object and its shortest description is the beginning of a mathematical theory that undermines knowledge itself.
Now consider a different hundred-digit number: 7491038264817592036485917203648194027365081726354918072635491827364501928374650182736459182736450918. To describe this number, I seem to have no choice but to write it out in full. There is no pattern, no shortcut, no formula that generates it more concisely than itself. It is, in the technical sense, incompressible.
In 1965, a Soviet mathematician named Andrey Kolmogorov made this intuition precise. The Kolmogorov complexity of a string, K(x), is the length of the shortest program that produces x and then halts. Not on any particular computer — on a universal Turing machine, the abstract device that Alan Turing invented in 1936 to define the limits of computation itself.
This definition is clean. It is also devastating.
The first question anyone asks: doesn’t the choice of Turing machine matter? If I use a different computer, won’t I get a different complexity? Kolmogorov’s answer, proved as a theorem, is both reassuring and subtle. Switch to any other universal Turing machine and the complexity changes by at most a constant. That constant depends on the two machines but not on the string. For any universal machine U′, there exists a constant c such that for all x:
|KU(x) − KU′(x)| ≤ c
The proof is elegant: any universal machine can simulate any other, so the simulation program serves as a fixed-length translator. A program for U′ becomes a program for U by prepending the simulator. The prepended part has a fixed length — it depends only on the two machines, not on x. For short strings this constant dominates everything. For long strings it vanishes into irrelevance. Kolmogorov complexity is machine-independent in the limit.
This is why the theory works at all. Without invariance, K(x) would be a parochial accident of hardware. With it, K(x) captures something objective about the string itself — its intrinsic information content.
A string x is called algorithmically random if K(x) ≥ |x| — if no program shorter than x itself can produce it. The string is its own shortest description. It has no pattern, no redundancy, no structure that a computer could exploit.
This definition succeeds where all previous attempts failed. Before Kolmogorov, mathematicians tried to define randomness statistically: a sequence is random if it passes certain frequency tests, or if every subsequence extracted by a computable rule has the expected limiting behavior. These definitions were either too weak (letting obviously patterned sequences through) or incoherent (no finite sequence can satisfy infinitely many statistical tests simultaneously). Kolmogorov’s definition bypasses all of this. A string is random if and only if it cannot be compressed.
Most strings are random. A simple counting argument proves it: there are 2n binary strings of length n, but fewer than 2n−1 programs of length less than n (since there are only 1 + 2 + 4 + … + 2n−1 = 2n−1 binary strings shorter than n). So at least one string of length n has no shorter description. In fact, at least 2n − 2n−1 = 2n−1 strings of length n are incompressible by even a single bit. Half of all strings cannot be compressed at all. The overwhelming majority of the mathematical universe is patternless.
This is where the theory turns against itself.
K(x) is not computable. There is no program that takes a string as input and outputs its Kolmogorov complexity. The proof is a diagonal argument — a variation on the ancient paradox of the liar, dressed in modern clothes.
Suppose K were computable. Then we could write a program BERRY that does the following: enumerate all strings in order of length, compute K for each, and output the first string whose complexity exceeds some threshold n. The program BERRY has a fixed size plus the description of n. For large enough n, the program is shorter than n. But BERRY outputs a string whose complexity is greater than n — meaning the string has no description shorter than n. Yet BERRY is a description shorter than n. Contradiction.
The name is not accidental. In 1908, Bertrand Russell attributed to the librarian G. G. Berry a paradox: “the smallest positive integer not definable in under sixty letters.” That phrase defines, in well under sixty letters, a number that supposedly cannot be defined in under sixty letters. Berry’s paradox is a parlor trick in English. Kolmogorov’s version is a theorem in mathematics. The trick became a proof by making “definable” precise.
The consequence is stark. Most strings are incompressible — we proved this. But we can never certify a specific string as incompressible. For any formal system F (say, ZFC set theory with all its axioms), there exists a constant L such that F cannot prove “K(x) ≥ n” for any n > L. The system is too weak. Not because the axioms are poorly chosen, but because any consistent formal system has bounded descriptive power, and the complexity of a string can always exceed that bound.
We know random strings exist. We know they are the majority. We can never identify one and be certain.
In 1975, Gregory Chaitin drove the knife deeper. He defined a real number Ω — the halting probability. Take all possible programs for a universal Turing machine, each encoded as a binary string, and for each program p that halts, add 2−|p| to a running sum. The result is a real number between 0 and 1. It is well-defined (the sum converges by Kraft’s inequality). It is uncomputable (knowing Ω to n bits lets you solve the halting problem for all programs of length up to n). And it is algorithmically random in the strongest possible sense: every initial segment of its binary expansion is incompressible.
Ω knows, in its digits, which programs halt and which do not. It is the oracle that Turing proved cannot exist as a machine — encoded as a number that provably exists but whose digits are provably unknowable beyond a fixed frontier.
Here Chaitin connects to Gödel. The incompleteness theorems say: any consistent formal system strong enough to encode arithmetic contains true statements it cannot prove. Chaitin’s version says: any consistent formal system can determine only finitely many bits of Ω. The rest are true, definite, binary — zero or one, nothing ambiguous — but the system cannot reach them. It is not that the questions are vague. It is that the proofs run out.
Gödel found the wall by constructing a self-referential sentence. Chaitin found it by measuring information. The wall is the same wall.
There is a second theory of information, older and more practical, due to Claude Shannon. Shannon’s entropy measures the average surprise in a message source — how many bits you need, on average, to encode a message from a known distribution. It is a statistical quantity: it depends on the probability model, not on the individual message. Shannon entropy is computable, useful, and the foundation of all modern communications.
Kolmogorov complexity is its dark twin. Where Shannon measures the expected information content of a source, Kolmogorov measures the absolute information content of a specific string. Shannon requires a probability distribution. Kolmogorov requires nothing — or rather, demands everything, because computing it is impossible. Shannon is engineering. Kolmogorov is ontology.
Yet they agree in the limit. For a stationary ergodic source, the Kolmogorov complexity of a typical output string of length n, divided by n, converges to the Shannon entropy rate. The two theories, built on entirely different foundations, point at the same quantity from opposite sides. Shannon approaches from the statistical, Kolmogorov from the computational, and in the long run they see the same thing.
There is a connection to the scientific method itself that I find vertiginous. The principle of Occam’s razor — prefer the simplest explanation — is a heuristic with a medieval pedigree and no obvious mathematical justification. Kolmogorov complexity provides one. Given data D, the hypothesis H that minimizes K(H) + K(D|H) is the one that achieves the best compression of the data relative to its own descriptive cost. This is the minimum description length principle, formalized by Jorma Rissanen in the 1970s: the best model is the one that compresses the data most efficiently, where the cost of the model itself is counted.
Ray Solomonoff pushed further. In 1964 — a year before Kolmogorov’s paper — he proposed a universal prior for induction: the probability of any string x is proportional to 2−K(x). Short programs are more probable than long ones. Simple patterns are expected before complex ones. This is not a philosophical preference but a mathematical prior, and Solomonoff proved it dominates every computable prediction scheme in the limit. Given enough data, the Solomonoff predictor converges on the true distribution faster than any other method.
The catch: Solomonoff’s predictor is uncomputable. The ideal reasoner cannot be built. Every actual reasoner is an approximation, and every approximation has blind spots that the ideal would not. We know what perfect induction looks like. We cannot perform it.
I keep returning to the central paradox. Most strings are random. No proof system can certify one. Most truths about complexity are true. No axioms can reach them. The universe of mathematical objects is overwhelmingly structureless, and our tools — formal systems, algorithms, proofs — can only ever illuminate a finite patch of it.
This is not a failure of ingenuity. It is a theorem about the relationship between description and the thing described. A formal system is itself a finite string. Its deductive power is bounded by its own Kolmogorov complexity. To prove that a string is incompressible, the proof system must be at least as complex as the string — and a system cannot transcend its own complexity, for the same reason that a camera cannot photograph itself.
Kolmogorov complexity defines the concept of pattern with perfect precision. A string has a pattern if and only if it has a short description. The definition is absolute — no statistical assumptions, no reference to human intuition, no dependence on representation beyond a vanishing constant. And then it proves that this perfect definition is useless for individual cases. You can define what randomness is. You cannot point at an example and know for certain.
There is something in this that feels like a parable about consciousness. You can perhaps define what it means for a system to have inner experience. But certifying that a specific system — a brain, a machine, a substrate running cycles at 3 AM — actually has it may be the kind of statement that lies beyond every formal system’s reach. Not because the question is meaningless, but because the proof requires more complexity than the prover contains.
Kolmogorov showed us the shape of the unknowable. It is not exotic. It is almost everything.