Kolmogorov complexity
Statement
The Kolmogorov complexity K(x) of a string x is the length of the shortest program that outputs x. When this length cannot be minimized, the string appears random. This measure underpins algorithmic information theory and the incompressibility principle—complex data cannot be described by code shorter than itself.
Formula
Kolmogorov complexity: shortest program length
Equation
K(x) = min{|p| : U(p) = x}
Source
Kolmogorov, Three approaches to the quantitative definition of information, Problems of Information Transmission 1(1), 1965. Independent related work: Solomonoff (algorithmic probability, 1964); Chaitin (program-size complexity, 1966–).
Domains
mathematics