Kolmogorovkompleksitet

Kolmogorovkompleksitet, commonly referred to as Kolmogorov complexity, is a measure of the information content or randomness of a finite object, most often a binary string. For a fixed universal computing device U, the Kolmogorov complexity K_U(x) is the length of the shortest program p that outputs x when run on U. The choice of U affects the value only up to an additive constant, an idea formalized by the invariance theorem: for any two universal machines U and V, there exists a constant c such that K_U(x) ≤ K_V(x) + c for all x.

Kolmogorovkompleksitet is not computable in general; there is no algorithm that, given an arbitrary x, determines K_U(x). This undecidability is closely tied to fundamental limits of algorithmic description and to the halting problem.

Two common variants are the plain complexity K(x) and the prefix-free (or prefix) complexity K_PC(x). The latter restricts valid programs to be prefix-free, which yields tighter theoretical bounds. One can also consider conditional Kolmogorov complexity K(x|y), the complexity of x given y as an auxiliary input.

Relation to compression and randomness is central. If a string is highly compressible, K(x) is small relative to its length; conversely, strings that appear random have K(x) close to the string length. For most strings of length n, K(x) is at least n − O(1). In randomness theory, prefixes of infinite sequences are deemed algorithmically random when their Kolmogorov complexity is high, a notion linked to Martin-Löf randomness.

History and impact: Kolmogorovkompleksitet was introduced in the 1960s by Andrey Kolmogorov, Gregory Chaitin, and Leonid Levin, forming a core concept in algorithmic information theory and the study of information content, description length, and randomness.