Kolmogorov Complexity — Mathematics Knowledge System

Overview

Kolmogorov complexity K(x) of a string x is the length of the shortest computer program (in a fixed universal Turing machine) that outputs x and halts. It formalizes the intuitive notion of 'information content' or 'randomness' of an individual string, without reference to any probability distribution. A string is called algorithmically random (incompressible) if K(x) ≈ |x|: it has no shorter description than itself. Kolmogorov complexity is uncomputable in general (by reduction to the halting problem), but is definable and can be bounded. It connects information theory, computability theory, and probability theory.

Intuition

Consider two strings: '010101010101010101010101' (alternating 01s, length 24) and a genuinely random 24-bit string. The first has a short description: 'print 01 twelve times' — maybe 20 characters of program. The random string has no shorter description than itself: you must list all 24 bits. Kolmogorov complexity captures this — the alternating string is simple (small K), the random string is complex (K ≈ length). This is the algorithmic analog of entropy, but for individual strings rather than probability distributions.

Formal Definition

Definition

Fix a universal Turing machine U. The Kolmogorov complexity (prefix complexity) of a string x is:

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

Kolmogorov complexity

|K_U(x) - K_V(x)| \leq c_{U,V}

Invariance theorem: complexity differs by at most a constant across universal Turing machines

K(x) \leq |x| + c

Trivial upper bound (copy program)

\Pr_{x \sim \{0,1\}^n}[K(x) < n - k] \leq 2^{-k}

Most strings are incompressible

K(xy) \leq K(x) + K(y) + c

Subadditivity

Notation

Notation	Meaning
$K(x)$	Kolmogorov complexity of string x
$K(x\|y)$	Conditional complexity of x given y
$U$	Fixed universal Turing machine

Theorems

Theorem 1: Invariance Theorem

For any two universal Turing machines U and V, there exists a constant c_{U,V} such that for all strings x, |K_U(x) - K_V(x)| \leq c_{U,V}. Thus K(x) is well-defined up to an additive constant.

Theorem 2: Incompressibility / Majority of Strings Are Random

For each n, at least 2^n - 2^{n-k+1} strings of length n satisfy K(x) \geq n - k. In particular, most strings are incompressible: for any c > 0, at most 2^{n-c} strings x of length n have K(x) \leq n - c.

Theorem 3: Kolmogorov Complexity Is Uncomputable

The function x \mapsto K(x) is not computable. If it were, one could solve the halting problem. However, K(x) is upper-semicomputable: it can be approximated from above.

Worked Examples

1
A short Python program: 'print("0"*16)' — about 18 characters of ASCII.
$K(x) \lesssim 18 \text{ bytes} \approx 144 \text{ bits}$
2
But more fundamentally, we need only specify the pattern and length. The description 'n zeros for n=16' takes O(log n) bits.
$K(x) = O(\log n) \text{ bits}$
3
Since |x| = 16 bits, K(x) ≪ |x| — this string is highly compressible.
$K(x) \ll |x| = 16$

✓ Answer

K(x) = O(log 16) = O(4) bits — far less than the string length 16 bits. A regular string like this has very low complexity.

Practice Problems

Mediumfree response

Why does the existence of a 'super-compression' algorithm that always halved K(x) lead to a contradiction?

Mediumapplication

Explain how Kolmogorov complexity captures the notion of 'randomness' for individual strings, and why Shannon entropy cannot do the same.

Common Mistakes

Common Mistake

Thinking K(x) depends on which programming language or compression algorithm you use.

The invariance theorem guarantees K(x) differs by at most a constant (the length of the 'translator' program) regardless of the universal machine. The choice of machine is fixed once.

Common Mistake

Confusing K(x) with the output of gzip(x) or any specific compressor.

gzip gives an upper bound on K(x) but is far from optimal for most x. K(x) is a theoretical minimum over all possible programs.

Quiz

Historical Background

The idea of measuring the complexity of an individual object by the length of its minimal description was independently developed by Kolmogorov, Solomonoff, and Chaitin in the 1960s. Solomonoff (1960) used it for inductive inference. Kolmogorov (1965) gave the formal definition in terms of algorithms. Chaitin (1966) developed the theory further and connected it to Gödel incompleteness. The invariance theorem — that the choice of universal Turing machine affects K(x) by at most a constant — is fundamental to the theory's coherence.

1960
Solomonoff introduces algorithmic probability for inductive inference.
Ray Solomonoff
1965
Kolmogorov defines algorithmic complexity and proves the invariance theorem.
Andrey Kolmogorov
1966
Chaitin independently develops algorithmic information theory; links to Gödel's incompleteness.
Gregory Chaitin
1975
Martin-Loef defines algorithmic randomness using Kolmogorov complexity.
Per Martin-Loef

Summary

Kolmogorov complexity K(x) is the length of the shortest program (for a fixed universal TM) that outputs string x — the algorithmic information content of x.
The invariance theorem ensures K(x) is well-defined up to an additive constant independent of the choice of universal Turing machine.
K(x) is uncomputable in general but is upper-semicomputable: any specific upper bound K(x) ≤ c is eventually verifiable.
The average Kolmogorov complexity E[K(X)] ≈ H(X) for a random variable X, linking algorithmic information to Shannon entropy.

References

BookLi, M. and Vitanyi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications, 3rd ed. Springer.
BookCover, T. and Thomas, J. (2006). Elements of Information Theory, 2nd ed. Wiley. Ch. 14.
WebsiteWikipedia — Kolmogorov complexity