Algorithmic information theory

Algorithmic information theory (AIT), also known as Kolmogorov complexity theory, is the study of the information content of individual objects — strings, numbers, data structures — measured not by their length or their Shannon entropy but by the length of the shortest program that produces them. Founded independently by Andrey Kolmogorov, Ray Solomonoff, and Gregory Chaitin in the 1960s, AIT inverts the usual relationship between theory and data: rather than assuming a probability distribution and measuring how surprising a particular outcome is, AIT asks what the data itself reveals about the simplest theory that could have generated it.

The central quantity is Kolmogorov complexity K(x): the length of the shortest program (in a fixed universal programming language) that outputs the object x and then halts. The choice of programming language affects the absolute value by only an additive constant — the length of the compiler between languages — which makes K(x) an objective measure of the object's algorithmic information content up to that constant. An object is algorithmically random if its Kolmogorov complexity is approximately equal to its length: no compression is possible, and the object contains no computable regularity.

The Foundational Results

AIT produces several results that are technically straightforward but philosophically radical:

Incomputability of Kolmogorov complexity. There is no general algorithm that can compute K(x) for arbitrary x. This is not a practical limitation but a mathematical one: any program that claims to compute K(x) for all x can be used to construct a paradox (the Berry paradox in algorithmic form), proving that the claim is false. The incomputability means that algorithmic information is not a quantity we can calculate exactly, only bound from above (by exhibiting a program) and sometimes from below (by proving that no shorter program exists).

The halting problem connection. Kolmogorov complexity is deeply connected to the undecidability of the halting problem: to know whether a program is the shortest one for a given output, you would need to know whether shorter programs halt — and you cannot know that in general. This makes AIT a meeting ground between information theory and computability theory, between what is knowable about data and what is computable about programs.

Algorithmic probability. Solomonoff's induction framework defines the prior probability of a data string as the sum over all programs that produce it, weighted by 2^{-length(program)}. This provides a universal prior for inductive inference — a formalization of Occam's razor in Bayesian terms. The framework is theoretically elegant but computationally intractable, making it more a normative ideal than a practical tool.

Applications and Generalizations

Despite its incomputability, AIT has generated important applications and conceptual frameworks:

Minimum description length (MDL) is the computable approximation of Kolmogorov complexity used in statistical model selection: choose the model that minimizes the sum of the length of the model description and the length of the data encoded relative to that model. MDL formalizes the trade-off between model complexity and fit, and it has become a standard principle in machine learning and statistical inference.

Algorithmic randomness provides a rigorous definition of what it means for an individual object to be random — not unpredictable