Algorithmic Information Theory

Core Idea

Algorithmic information theory (AIT) studies information content through the lens of computation, building on Kolmogorov complexity to develop a complete theory of individual-sequence randomness, algorithmic probability, and the limits of mathematical reasoning. A string is algorithmically random if it is incompressible — no program significantly shorter than the string itself can produce it. Chaitin's constant Omega (the halting probability of a universal prefix-free Turing machine) is a real number that is algorithmically random, well-defined, but uncomputable. AIT provides the foundations for Solomonoff induction (a universal theory of prediction), the minimum description length principle in statistics, and connects to Godel's incompleteness theorems.

Explainer

Shannon's information theory is fundamentally probabilistic: entropy, mutual information, and capacity all require a probability distribution. Algorithmic information theory takes a different approach: it measures information content through the lens of computability, asking how much computational work is needed to produce a given object. The central object is Kolmogorov complexity K(x), and AIT builds an entire theory around it.

The first major result is a rigorous definition of randomness. In Shannon's framework, "random" means "drawn from a distribution." But what makes an individual string random? AIT answers: x is algorithmically random if K(x) >= |x| - c, meaning no program significantly shorter than x can produce it. This captures the intuition that random strings have no patterns, no shortcuts, no compressibility. The counting argument shows that most strings are random in this sense — structure and compressibility are the exception.

The second major result is algorithmic probability and Solomonoff induction. The algorithmic probability of x is m(x) = sum over {p : U(p) = x} 2^-|p|, the probability that a random program produces x. This is dominated by the shortest program, so m(x) ≈ 2^(-K(x)). Solomonoff showed that using m as a prior for prediction yields a universal prediction scheme that converges to the truth for any computable data source. This is the deepest formalization of Occam's razor: prefer the simplest (shortest-description) explanation, weighted by its complexity.

The third pillar connects AIT to the foundations of mathematics. Chaitin showed that for any formal system (like ZFC set theory), there exists a constant c such that the system cannot prove "K(x) > c" for any specific string x, even though most strings have K above any finite threshold. This is an information-theoretic version of Godel's incompleteness: a formal system with finite information content (its axioms) cannot establish facts about strings with more information content than the system itself. The halting probability Omega encodes the solution to every finite mathematical problem in its digits, yet no algorithm can compute those digits — it is a single real number containing infinite compressed information that is provably inaccessible.