Why No Algorithm Can Compress Every File: A Counting Proof — Epoche B2
Many people believe that a sufficiently clever algorithm could compress any file, at least a little. Commercial software sometimes encourages this hope, and its strongest form — that a file could be compressed, then compressed again, and so on down to a few bytes — is still occasionally offered for sale. Yet the belief is provably false, and the proof requires nothing more advanced than counting. This essay states the claim, gives the deductive argument, and then shows how the idea leads to a precise definition of randomness and to a limit on what any program can know about its own output. What a lossless compressor must be Compression is lossless when the original file can be recovered exactly. That requirement has an immediate mathematical consequence: the compression map must be injective , or one-to-one, meaning that no two distinct inputs are sent to the same output. If two different files compressed to the same string, the decompressor, seeing that string, would have no way of knowing which to return, and one of the two would be lost. Injectivity is not an extra assumption; it is what "lossless" means, restated. Everything else follows from counting how many outputs are available. A binary string of length $k$ is a sequence of $k$ symbols, each independently $0$ or $1$; multiplying the choices position by position gives $2^{k}$ such strings. The count includes $k = 0$, the empty string, of which there is exactly $2^{0} = 1$. The counting argument There are exactly $2^n$ binary strings of length $n$. The number of binary strings shorter than $n$ bits is the sum over all shorter lengths, $$\sum_{k=0}^{n-1} 2^k \;=\; 2^n - 1 \; The middle equality is worth deriving rather than quoting. Write $S = 1 + 2 + 4 + \cdots + 2^{n-1}$. Doubling gives $2S = 2 + 4 + \cdots + 2^{n}$, which is the same list with the leading $1$ removed and $2^{n}$ appended. Subtracting, $2S - S = 2^{n} - 1$, so $S = 2^{n} - 1$. Now apply the pigeonhole principle : if objects are placed into boxes and there are more objects than boxes, some box must receive two objects. Here the objects are the $2^n$ strings of length $n$ and the boxes are the $2^n - 1$ strictly shorter strings. If every string of length $n$ were compressed to something shorter, two of them would have to share an output, and the map would not be injective. So there are not enough short descriptions to go round: at least one string of length $n$ cannot be compressed at all. Sharpening it: how few strings compress well The argument gives more than one stubborn string. Ask how many strings of length $n$ can be shortened by more than $c$ bits — that is, sent to an output of length at most $n - c - 1$. By the same sum, the number of available outputs is $2^{n-c} - 1$, which is fewer than $2^{n-c}$. Since the map is injective, at most that many inputs can be so compressed, and the fraction of length-$n$ strings among them is below $$\frac{2^{n-c}}{2^{n}} = 2^{-c}.$$ For $c = 10$, the fraction is below $2^{-10} = 1/1024$: fewer than one string in a thousand of any given length can be shortened by more than ten bits. For $c = 20$, fewer than one in a million can be shortened by more than twenty. The bound depends only on $c$, not on $n$, and not at all on how clever the algorithm is. Why a compressor must sometimes lengthen For strings of a single fixed length, this counting shows only that few strings can be shortened — not that any must be lengthened. But a real compressor must be defined on all finite strings, and there the conclusion is exact. Consider the set $S_m$ of all strings of length at most $m$, which by the sum above contains $2^{m+1} - 1$ members. Suppose a compression map is injective and never lengthens any input. Then it sends every member of $S_m$ to a member of $S_m$, since the output is no longer than the input. An injective map from a finite set into itself must be onto — the images are distinct, so they exhaust the available places — and is therefore a permutation, a rearrangement of $S_m$ among itself. A permutation preserves the multiset of lengths exactly. Consequently, any scheme that shortens even one input must lengthen at least one other, and no injective map can reduce the total, and hence the average, length over the set of all strings of length at most $n$. The dream of repeated compression dies here: each pass would have to shorten the previous output, and after enough passes every file would have to fit in a handful of bits, which the first argument has already excluded. From counting to Kolmogorov complexity Kolmogorov complexity turns this observation into a definition of what it means for a string to have no pattern. Begin from an everyday idea: a string is simple if you can describe it briefly. The digits of $10^{6}$ zeros can be described in a sentence; a million coin flips cannot be described more briefly than by listing them. To make "describe" precise, fix a universal machine $U$ — formally a Turing machine that can simulate any other machine given a description of it, and informally just a programming language together with an interpreter for it. The complexity $K(x)$ of a string $x$ is the length in bits of the shortest program for $U$ that outputs $x$ and halts: $$K(x) = \min\{\, |p| : U(p) = x \,\}.$$ (The standard treatment additionally requires programs to be self-delimiting, so that one program's code cannot be a prefix of another's and two programs can be concatenated unambiguously. The counting results below are unaffected by this refinement.) The obvious objection is that $K$ depends on the language chosen, and the invariance theorem answers it with an argument short enough to give in full. Let $U$ and $V$ be two universal machines. Because $U$ is universal, there is a program $s$ for $U$ that interprets $V$-programs — an interpreter, whose length $|s|$ is a fixed number determined by the two machines and by nothing else. Given the shortest $V$-program $p$ for $x$, the concatenation of $s$ with $p$ is a $