Kolmogorov Complexity

Kolmogorov complexity measures a string's information as the length of the shortest program that outputs it.

Definition

The Kolmogorov complexity of a string is the length of the shortest program, on a fixed universal computer, that prints the string and halts. It captures the string's intrinsic, algorithmic information content.

Structure versus randomness

A string with a pattern, such as a million repetitions of 01, has low complexity because a short loop generates it. A truly random string has complexity near its own length: the shortest description is essentially the string itself.

Uncomputability

No algorithm can compute Kolmogorov complexity for all inputs. A proof by contradiction, echoing Berry's paradox, shows that a complexity-computing program could describe a string more briefly than its own complexity allows. It is only approximable from above.

Relation to entropy

For strings drawn from a probabilistic source, expected Kolmogorov complexity per symbol approaches the Shannon entropy. The two measures agree in the average, though Kolmogorov complexity applies to individual objects, not just distributions.

Why it matters

It gives a rigorous meaning to simplicity, formalizing Occam's razor in inductive inference and the theory of minimum description length. It also proves that no compressor can shrink every string — most strings are incompressible.

Practical shadow

Real compressors are computable upper bounds on Kolmogorov complexity: the smaller a file gzip produces, the more structure it found. The true minimum, though, remains forever out of reach.

python

# A short program with low Kolmogorov complexity output
print('01' * 1_000_000)   # tiny program, long string