Kolmogorov Complexity: The Randomness No Program Can Compute

A different way to define randomness

Shannon entropy measures the average information content of symbols drawn from a known probability distribution. Kolmogorov complexity, developed independently by Ray Solomonoff, Andrei Kolmogorov and Gregory Chaitin in the 1960s, asks a related but genuinely different question about a single specific string, with no probability distribution in sight at all: what is the length of the shortest possible program, in some fixed reference language, that outputs exactly this string and then halts?

K(x)  =  length of the shortest program p such that  U(p) = x

// U is a fixed universal computer (a universal Turing machine)
// K(x) is measured in bits — the length of p's encoding, not the length of x

Why some strings are compressible and others fundamentally are not

Consider two 1,000-character strings. The first is a thousand copies of the digit “1”. The second is generated by flipping a fair coin a thousand times. The first has a tiny Kolmogorov complexity — a program as short as print("1" * 1000) reproduces it exactly, regardless of which reference language you pick (up to a small constant for the interpreter overhead). The second, if it is a genuinely random sequence with no exploitable pattern, has no shorter description than essentially quoting the string itself — any program that outputs it must, in the worst case, be at least as long as the string it produces, because there simply is no shorter rule that generates that exact sequence of coin flips and nothing else.

This gives Kolmogorov's own formal definition of randomness: a string is algorithmically random if its Kolmogorov complexity is close to its own length — if the shortest possible description of it is not meaningfully shorter than just writing it out. This is a fundamentally different notion from Shannon's, and the two can disagree on a single realized string: a fair coin flipped a thousand times has high Shannon entropy as a source (each flip genuinely carries close to 1 bit of information on average, before you see the result), but any specific realized sequence produced by that source is, with overwhelming probability, algorithmically random in Kolmogorov's sense too — the two measures agree in the typical case, which is not a coincidence, but they are conceptually answering different questions (a source's average uncertainty, versus one particular string's shortest description).

The proof it is uncomputable, in one paragraph

Here is the sharpest and most famous result in the field: K(x) cannot be computed by any algorithm, for any x, in general. The classic proof is a Berry-paradox-style argument by contradiction. Suppose a program COMPLEXITY(x) existed that always correctly computed K(x). Then you could write a short program that searches through all strings in order and outputs the first one whose Kolmogorov complexity, as reported by COMPLEXITY, exceeds some large bound N — call it “the first string with complexity greater than N describable in fewer characters than N”. But that search-and-print program, plus the fixed encoding of N, is itself a description of that string using far fewer than N bits (the search logic is a small constant, and N itself only takes about log2(N) bits to encode) — directly contradicting the claim that the string's shortest description needs more than N bits. The contradiction is unavoidable for any N large enough that log(N) plus a constant is less than N, which forces the conclusion that no COMPLEXITY function computing K(x) exactly can exist at all.

This is not a practical limitation waiting on faster computers or smarter algorithms — it is a hard mathematical result, in the same family as Turing's halting problem and Gödel's incompleteness theorems (all three, not coincidentally, rest on the same self-referential, diagonalization-style argument structure). You cannot verify that a candidate short program is truly the shortest one that produces a given string, because doing so in general would require solving the halting problem — checking every shorter candidate program to see whether it halts and outputs x, and some of those candidates simply never halt.

Compression as an honest, computable proxy

Since K(x) itself is unreachable, practitioners use compressed length under a specific, fixed, real compression algorithm as a computable stand-in — an upper bound on K(x), because the decompressor plus the compressed data together form one valid, if not necessarily minimal, program that reproduces x. Any general-purpose lossless compressor works as this proxy, and LZ77 — the algorithm underlying gzip, DEFLATE, and this page's live demo — is one of the clearest to see in action, because its output visibly separates the compressible and incompressible parts of a string.

LZ77 sliding-window compression, the core idea:
  scan forward through the string
  at each position, look BACKWARD in a bounded window for the longest
  match to what comes next
  if a match of length >= some minimum is found:
    emit a (distance, length) BACK-REFERENCE instead of the raw characters
  else:
    emit the literal character(s), uncompressed

// a highly repetitive string collapses to a handful of back-references
// a genuinely random string finds almost no matches and stays close
// to its original length -- the compressed size IS the honest proxy

Run LZ77 on the thousand-ones string and it collapses to a handful of bytes — one literal “1” plus a single long back-reference repeated, or run-length-encoded outright. Run it on a thousand genuine coin flips and it barely shrinks at all, because there are no repeated substrings long enough to exploit; the compressed length sits close to the original length, which is exactly the signature Kolmogorov's definition predicts for an algorithmically random string. The compressed size is only an upper bound — a smarter compressor, or a cleverer hand-written program exploiting some subtler pattern LZ77 cannot see, might always find something shorter — but as a practical, computable, honest estimate of “how compressible is this specific string”, it is the right tool for the job, and it is exactly what the live demo on this page runs against whatever bit-string you give it.

Where uncomputability shows up as a practical wall

Kolmogorov complexity's uncomputability is not just a curiosity — it underlies concrete limits elsewhere. It gives a rigorous, distribution-free foundation for Occam’s razor in machine learning and Solomonoff's theory of inductive inference (favouring the shortest hypothesis consistent with the data is provably the right prior, in a precise algorithmic-probability sense). It also connects directly back to Chaitin's incompleteness theorem: for any consistent formal axiomatic system, there is a computable bound past which the system cannot prove the exact Kolmogorov complexity of any specific string, even though every string obviously has some definite complexity value — provability and truth come apart here in the same way Gödel showed they come apart for arithmetic itself.

Frequently asked questions

Try it live

Everything above runs in your browser — open Kolmogorov Complexity and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.