Kolmogorov Complexity

Flip a fair coin ten times and get ten heads. Flip it again and get HTHTTHHTHT. Both sequences have probability $1/1024$, yet only one of them looks like a fair coin. Whatever makes one sequence feel random and the other not, it has to be a property of the sequence itself, not of the distribution that produced it.

Kolmogorov complexity is that property, made precise.

The definition#

For a string $x$, look at every program that outputs $x$ and halts. The length of the shortest one is the Kolmogorov complexity of $x$:

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

where $U$ is a fixed universal Turing machine and the minimum runs over programs $p$ that halt with output $x$.

Three examples calibrate the definition.

• A string of one billion zeros has a tiny program: print("0" * 10**9). $K$ is a few dozen bits, against a billion bits of string.
• A short jumble like j7$kQ2m!xR has no visible pattern. As far as anyone can tell, the shortest program just prints it literally, so $K$ is roughly the length of the string. That is the typical case.
• A megabyte of cryptographic PRNG output looks random to every efficient test, but the generator code plus its seed is a few hundred bytes, so $K$ of the whole megabyte is a few hundred bytes. Random-looking and algorithmically random are different things, and the gap between them is most of this subject.

You have met $K$ in disguise: every compressor is searching for a shorter description of its input. gzip shrinks the zeros to almost nothing and barely touches the jumble. $K$ is the limit all compressors reach toward, and as we are about to see, none of them can ever reach it.

Two technical notes that matter later. Programs must halt, otherwise a looping program could be said to "produce" anything at all. And programs are self-delimiting: no program is a prefix of another, as if each one ends with an explicit stop marker.

Why the choice of language doesn't matter#

$K$ apparently depends on the programming language. Python and machine code give different lengths for the same string. The invariance theorem dissolves the worry: for any two universal machines $U$ and $V$ there is a constant $c$, depending only on the pair, with

$$\left|K_U\right(x)-K_V(x\left)\right|\le c\text{forevery}x.$$

Pause and try: can you see the one-line proof?

Write an interpreter for $V$ in $U$'s language. Its length is the constant $c$. Any program for $V$ runs on $U$ by prepending the interpreter, so $K_U\left(x\right)\le K_V\left(x\right)+c$, and by symmetry the other direction holds too. The constant depends on the machine pair, never on the string.

So $K$ is well defined up to an additive constant, the same way asymptotic complexity is well defined up to constant factors. For long strings, the choice of language washes out.

Most strings are incompressible#

How many strings can be compressed at all? Count. There are $2^n$ binary strings of length $n$, but the programs shorter than $n$ number at most $1+2+4+\cdots +2^{n-1}=2^n-1$. The programs run out before the strings do, so some string of length $n$ has $K\left(x\right)\ge n$.

The same count says much more: fewer than $2^{n-c}$ strings can have $K\left(x\right)<n-c$, so the fraction of strings within $c$ bits of incompressible is at least $1-2^{-c}$. At $c=10$, that is 99.9 percent of all strings. At $c=100$, the compressible exceptions are one in ${10}^{30}$.

This flips the intuition. Structure is the rare case. A string drawn at random almost certainly has complexity close to its length.

Notice what kind of proof this was: we showed incompressible strings exist by counting, without exhibiting a single one. That is not laziness. It is the next theorem.

You cannot compute K#

The Oxford librarian G. G. Berry pointed Bertrand Russell at a puzzle Russell published in 1906. In one common telling, the phrase

the smallest positive integer not nameable in fewer than twenty English words

names, in twelve words, an integer that supposedly needs twenty. English is too fuzzy for the paradox to bite. Kolmogorov complexity is not.

Suppose $K$ were computable. Write the procedure findComplex(L): walk all strings in order, call $K$ on each, return the first with $K\left(x\right)>L$. The procedure's length is about $\log L$ plus a constant, because only the encoding of $L$ grows. Pick $L$ large enough that $\log L+c<L$, and the procedure becomes a program shorter than $L$ that outputs a string whose complexity exceeds $L$. But $K$ of a string is at most the length of any program producing it. Contradiction. $K$ is not computable.

Pause and try: where exactly does the argument use computability of K?

In the loop. findComplex must evaluate $K\left(x\right)$ to test $K\left(x\right)>L$. If $K$ is merely approximable from above (it is), the loop can never confirm that a string's complexity exceeds $L$; it would wait forever on strings whose compression it hasn't found yet. The contradiction only assembles if $K$ can be computed exactly.

The busy beaver numbers make the cost concrete. $BB\left(n\right)$ is the longest halting time of any $n$-state Turing machine on blank tape: $BB\left(1\right)=1$, $BB\left(2\right)=6$, $BB\left(3\right)=21$, $BB\left(4\right)=107$, and $BB\left(5\right)=47,176,870$, pinned down only in 2024. If we knew all of $BB$, we could compute $K$: enumerate every candidate program up to the trivial bound, run each for its busy-beaver budget, and the shortest that outputs $x$ is $K\left(x\right)$. Since $K$ is uncomputable, so is $BB$.

Chaitin's incompleteness#

The same argument, run inside a formal theory, proves something stronger. Fix a sound theory $T$ (say ZFC) and search all proofs in $T$ for one that establishes "$K\left(x\right)>L$" for some specific $x$. The searcher's length is a constant depending on $T$. Choose $L_T$ larger than that constant: if $T$ ever proved $K\left(x\right)>L_T$, the searcher would be a short program producing a string of provably high complexity, the same contradiction as before.

So a sound theory $T$ can prove $K\left(x\right)>L_T$ for no specific string, even though the counting argument shows the statement is true for almost all of them. Gödel built one unprovable sentence by self-reference. Chaitin gets an infinite family of true, unprovable statements with no self-reference at all. A finite system cannot certify more information than it contains.

Randomness without probability#

For infinite sequences, the definition you would guess is the right one: a sequence $\omega$ is algorithmically random when every prefix is incompressible, $K\left({\omega }_{1..n}\right)\ge n-c$ for all $n$. By the Levin-Schnorr theorem this coincides exactly with Martin-Löf's definition from probability theory: passing every effective statistical test. The law of large numbers and its relatives all fall out of incompressibility. Randomness becomes a property of one specific sequence, no distribution required.

The PRNG from earlier shows where the real boundary lies. Its output passes every test you can afford to run, but its prefixes have description length bounded by code plus seed, which never grows. The line is not between $K$ and statistics; it is between the tests you can run efficiently and the tests you cannot.

If you remember three things#

1. $K\left(x\right)$ is the length of the shortest halting program for $x$, well defined up to a constant that never depends on the string.
2. Almost every string is incompressible, but no specific string can be proved incompressible past a theory-dependent threshold.
3. Compression, computability, provability, and randomness are one subject: a finite description can certify only finitely much information.