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.

Symbol	Unicode	Name	Meaning
C(x)	—	Plain complexity	Shortest program length
K(x)	—	Prefix complexity	Prefix-free version
U	—	Universal machine	Reference interpreter
Ω	U+03A9	Chaitin's Omega	Halting probability

Metatheory. Uncomputable but upper semicomputable. Invariance makes it well-defined up to a constant. Unifies randomness, compression, and prediction; Chaitin's incompleteness bounds provable complexity within any theory.

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

Limitations. Not computable, only approximable from above. Additive constant obscures small objects. Depends on choice of universal machine within that constant.