Kolmogorov Complexity
Kolmogorov complexity measures the information content of a string as the length of the shortest program that outputs it. A string is algorithmically random if it cannot be significantly compressed.
Background
- Kolmogorov complexity is an information-theory concept: the complexity of a piece of data equals the length of the shortest computer program that can produce it. A random-looking string has high complexity (no short program generates it); a predictable pattern has low complexity.
- Named after Soviet mathematician Andrey Kolmogorov (1903-1987), who formulated it independently alongside Ray Solomonoff and Gregory Chaitin in the 1960s. It is the core of algorithmic information theory.
- Key fact: Kolmogorov complexity is not computable — no algorithm can find the shortest program for arbitrary data. This connects it to Gödel's incompleteness theorems and the halting problem.
- Practical relevance: underlies data compression (a compressed file is a short generating program), the Minimum Description Length principle in machine learning, and philosophical discussions of randomness and Occam's razor.