Symptom

You have two files, each exactly one megabyte.

The first is a megabyte of the byte 0x00. The second is a megabyte from /dev/urandom. Gzip the first and you get a few hundred bytes. Gzip the second and you get slightly more than a megabyte, because the header costs something and there is nothing to exploit.

Shannon (T018) does not quite explain this. Entropy is a property of a distribution, and you do not have a distribution — you have two specific files. Asking “what is the entropy of this file” is a category error, and yet the intuition that one file is simple and the other is complicated is obviously correct and obviously about the files themselves.

You need a notion of information content that applies to a single object. That is what Kolmogorov complexity is, and having it changes how you think about randomness, compression, and simplicity.

Statement

The Kolmogorov complexity $K(x)$ of a string $x$ is the length of the shortest program that outputs $x$ and halts, on some fixed universal machine $U$ (T013):

$$K(x) = \min\{|p| : U(p) = x\}$$

Three facts make it worth the trouble.

Invariance. For universal machines $U$ and $V$, there is a constant $c$ depending on the pair but not on $x$ with $|K_U(x) - K_V(x)| \le c$. Choice of language shifts every complexity by at most an additive constant, so $K$ is well-defined up to that constant.

Incompressibility. For every $n$ and $k$, at least $2^n - 2^{n-k} + 1$ strings of length $n$ have $K(x) \ge n - k$. Most strings are incompressible: at most one in $2^{k}$ can be compressed by $k$ bits, by counting.

Uncomputability. $K$ is not computable. No program takes $x$ and returns $K(x)$.

Define a string as random when $K(x) \ge |x|$: it has no description shorter than itself. This is the definition of randomness for individual objects — not “produced by a random process,” which is a claim about history, but “has no structure to exploit,” which is a claim about the object.

Argument

Invariance. $U$ can simulate $V$: there is a fixed interpreter program of some length $c$ that reads a $V$-program and runs it. So any $V$-description of $x$ becomes a $U$-description of length at most $|p| + c$. Symmetrically the other way. The constant is the size of an interpreter, and that is all.

This is why $K$ is meaningful. Rewriting your compressor in a different language does not change what is compressible, only the fixed overhead.

Incompressibility, by counting. Programs shorter than $n-k$ number at most $2^{n-k} - 1$. Each outputs at most one string. Strings of length $n$ number $2^n$. So at most $2^{n-k}-1$ of them have $K(x) < n-k$, leaving more than $2^n - 2^{n-k}$ with $K(x) \ge n-k$. At $k = 10$, fewer than one in a thousand strings compresses by ten bits.

This is exactly the pigeonhole fact behind “no compressor compresses everything.” Any lossless compressor that shrinks some inputs must expand others. The counting argument is not a limitation of current compressors; it is arithmetic.

Uncomputability, via Berry’s paradox. Suppose $K$ were computable. Write a program: for a fixed integer $m$, enumerate strings in order and output the first $x$ with $K(x) > m$. Such an $x$ exists by counting. Call this program $P_m$; its length is $\log m + c$ for some constant $c$ covering the enumeration and the call to $K$.

But $P_m$ outputs a string of complexity greater than $m$ using only $\log m + c$ bits. For $m$ large enough that $\log m + c < m$ — which holds for essentially every $m$ past a small threshold — we have a contradiction: $x$ is produced by a description shorter than $m$, so $K(x) \le \log m + c < m$.

Hence $K$ is not computable. This is “the smallest number not describable in fewer than twenty words,” made rigorous. It also reduces to the halting problem (T010): if you could compute $K$ you could solve halting, and conversely.

A subtlety worth knowing: $K$ is upper semi-computable. You can compute better and better upper bounds — run all programs in parallel by dovetailing and record the shortest that has produced $x$ so far. The estimate decreases monotonically toward $K(x)$ and never tells you when it has arrived. Every real compressor is an upper bound on $K$ that halts.

Relation to Shannon entropy. They agree on average. For a computable source with distribution $p$, the expected Kolmogorov complexity satisfies $H(p) \le \mathbb{E}[K(x)] \le H(p) + c$ for a constant depending on the source description. Shannon measures the average over the distribution; Kolmogorov measures the individual object; and the two coincide in expectation. That is the bridge between T018 and this post, and it is the reason both notions deserve the name “information.”

The incompressibility method. Because most strings are incompressible, you can prove things about typical objects by assuming randomness and deriving a contradiction. Want a lower bound on the average time of a sorting algorithm? Argue that a fast run on an incompressible input yields a short description of that input. This turns the counting argument into a proof technique, and it routinely gives one-paragraph proofs of results that take pages otherwise.

The incompressibility method, in one example. Claim: any algorithm sorting $n$ distinct items by comparisons needs $\Omega(n \log n)$ comparisons on average. Take a permutation $\pi$ with $K(\pi) \ge \log_2(n!) - 10$, which exists because at most one permutation in $2^{10}$ is that compressible. The sequence of comparison outcomes during the sort is a bit string that, together with the algorithm’s fixed description, reconstructs $\pi$ — replay the comparisons and you recover the input order. So the number of comparisons is at least $K(\pi) - c \ge \log_2(n!) - c’ = \Omega(n \log n)$ by Stirling.

The counting argument of T003 and this argument are the same argument, but the incompressibility version needs no decision-tree formalism and generalizes to average case for free, which is the sort of leverage the method gives.

Forbids

A universal compressor that compresses every input. By counting, not by engineering. Any claimed universal compressor either loses data or expands some inputs, and no amount of cleverness changes this.

Computing the true information content of your data. You cannot know the compression floor for a specific file; you can only exhibit compressors that get close from above.

A finite test for randomness. No program decides whether a string is Kolmogorov-random. Statistical tests check specific regularities and nothing more, so “passed the test suite” is not “random.”

Recursive compression. Compressing already-compressed data cannot keep gaining. If output were still compressible, the composition would be a shorter program, so good compression output looks random by construction.

Does not forbid

It does not make compression useless — real data is deeply non-random. Text, images, logs and source code sit in a vanishingly small structured corner of string space. zstd, Brotli and LZMA exploit exactly that. The theorem says most strings are incompressible, and real files are not typical strings; that gap is the entire compression industry.

It does not stop practical randomness testing. Dieharder, TestU01 and the NIST suite are used seriously to evaluate PRNGs, and they catch real defects. They cannot certify randomness, but they falsify it, and falsification is what you need to reject a bad generator.

It does not mean normalized compression distance cannot work. NCD — using gzip output sizes to approximate the information distance between two objects — does plagiarism detection, phylogeny reconstruction from genomes, and language clustering, and it does them well. The uncomputable quantity is approximated from above by a real compressor, and the approximation is good enough to be useful. A 2023 paper even got competitive text classification from gzip plus k-nearest-neighbours, beating some neural baselines on low-resource tasks.

It does not say cryptographic randomness is unattainable. /dev/urandom and ChaCha20-based CSPRNGs produce output that is computationally indistinguishable from random, which is not Kolmogorov randomness — the output has a short description, namely the seed — but it is the right notion for security. The two definitions of “random” answer different questions, and conflating them causes real confusion.

It does not make the constant irrelevant in practice. The invariance constant is asymptotic. For short strings, language choice dominates completely, which is why “the Kolmogorov complexity of this 20-byte string” is not a meaningful quantity, and why practical applications always work with large objects.

Boundary

  • Prefix complexity $K$ versus plain complexity $C$. Requiring the program set to be prefix-free makes Kraft’s inequality apply and the theory much cleaner, at the cost of $O(\log n)$ additive terms. It is what makes algorithmic probability and Chaitin’s Omega well-defined.
  • Conditional complexity $K(x \mid y)$ is the shortest program producing $x$ given $y$ for free. Information distance and NCD are built on it, and it is the algorithmic analogue of conditional entropy.
  • Time-bounded complexity $K^t$. Restrict to programs running within $t$ steps and you get a computable quantity. That is what real compressors approximate, and the theory of $K^t$ connects directly to pseudorandomness and to the barriers in T030.
  • Levin’s universal search. Dovetail over all programs, giving program $p$ a fraction $2^{-|p|}$ of the time. This solves any inverse problem within a constant factor of optimal, and the constant is astronomically bad. It is the cleanest example of a theoretically optimal, practically useless algorithm.
  • Solomonoff induction. Weight every hypothesis by $2^{-K}$ and you get a universal predictor that dominates every computable predictor — uncomputable, and the formal ancestor of Occam’s razor, which is the next post’s subject.