Kolmogorov Complexity

Origin. Solomonoff (1960), Kolmogorov (1965), Chaitin (1966). Algorithmic information theory. Measures the information content of an individual object by its shortest description.

Models. The complexity of a string is the length of the shortest program that outputs it on a universal machine. Randomness is incompressibility. Object-level rather than distributional information.

Formalism.

Plain complexity: C(x) = min{ |p| : U(p) = x }. Length of shortest program for x on universal U.

Invariance theorem: For universal U, V: C_U(x) ≤ C_V(x) + c_{U,V}. Machine-independent up to an additive constant.

Prefix complexity: K(x): programs drawn from a prefix-free set. Satisfies Kraft inequality; enables algorithmic probability.

Conditional complexity: C(x | y): shortest program for x given y.

Incompressibility: Counting: most strings of length n have C(x) ≥ n − O(1). Random string = incompressible string.

Uncomputability: C is not computable (a computable C would solve halting-like problems). Upper semicomputable: approximable from above.

Chaitin's Ω: Halting probability Ω = Σ_{p halts} 2^{−|p|}. Algorithmically random real; its bits are incompressible.

Symbols.

Metatheory. The invariance theorem — proved independently by Solomonoff, Kolmogorov and Chaitin — is what makes the definition a definition: for universal U and V the complexities differ by a constant depending only on the pair, so the function is well defined up to O(1). C is upper semicomputable and not computable, and in fact C ≡_T ∅′, so exact values carry the full strength of the halting problem. Chaitin's incompleteness theorem (1974) sharpens this into a proof-theoretic bound: for each sound effectively axiomatized theory T there is a constant c_T beyond which T proves no statement of the form C(x) > n, so a theory can certify only boundedly much randomness, and c_T is roughly the complexity of T's own axioms. Martin-Löf's oscillation theorem shows plain complexity cannot serve for infinite sequences — for every X there are infinitely many n with C(X↾n) < n − c — which is why prefix complexity was introduced; the Levin–Schnorr theorem then gives the correct characterization, X is Martin-Löf random iff K(X↾n) ≥ n − O(1). Kučera and Slaman (2001) proved every left-c.e. Martin-Löf random real is the halting probability of some universal prefix machine, so Ω is not one number but a class.

Applies to. Algorithmic randomness. Minimum description length. Solomonoff universal induction. Information-theoretic incompleteness. Data compression theory.

Limitations. The additive constant is not a technicality that can be worked around: for any string x a suitably perverse universal machine makes C(x) = 1, so no claim about the complexity of a particular finite object is machine-independent, and the theory has content only asymptotically or in the presence of a fixed reference machine chosen by convention. Nothing is computable — C is only approximable from above, and Chaitin's bound means a fixed theory can prove only finitely many lower bounds, so the strings the theory declares random are almost all strings it cannot certify. Resource-bounded variants do not inherit the clean invariance, since simulation overhead now enters the comparison, and no time-bounded version has the same canonical status. Solomonoff's universal prior is not computable, so the optimality theorem for universal induction describes a predictor that cannot be run. The measure conflates structure with noise: a uniformly random string has maximal complexity and no content at all, which is the defect the structure function and sophistication were introduced to repair.

© 2026 Lingenic LLC