Kolmogorov Complexity
Kolmogorov complexity measures the information in a string by the length of the shortest program that produces it.
Information as program length
The Kolmogorov complexity of a string is the length of the shortest program that outputs it and halts, on a fixed universal machine. A string with a short description, like a million repetitions of "01," has low complexity. A truly random string has complexity close to its own length, because nothing shorter generates it.
Compressibility and randomness
This gives a rigorous meaning to randomness: a string is random if it is incompressible, meaning no program shorter than the string produces it. Most strings are incompressible, because there are far more long strings than short programs. Randomness, formalized this way, is the absence of any exploitable pattern.
It is uncomputable
No algorithm can compute Kolmogorov complexity in general. If one could, you could find the shortest description of any string, which leads to a contradiction related to the halting problem and the Berry paradox ("the smallest number not describable in few words"). The measure is well-defined but not computable.
Invariance
The complexity depends on the choice of universal machine, but only up to an additive constant: switching machines changes every string's complexity by at most a fixed amount, the length of an interpreter. This invariance theorem makes Kolmogorov complexity a robust, machine-independent notion for long strings.
Uses
- Formalizing randomness and the foundations of probability
- Proving lower bounds via incompressibility arguments
- Grounding Occam's razor: prefer the shortest explanation
- Connecting to entropy in information theory
Relation to practical compression
Real compressors like gzip find some short description, giving an upper bound on Kolmogorov complexity but never the true minimum. The gap reflects that finding the shortest program is uncomputable. Still, the idea that compressibility measures structure guides real data analysis and model selection.