Algorithmic Probability

Algorithmic probability, also known as Solomonoff probability, measures the likelihood that a randomly sampled program, when executed on a universal Turing machine, will generate a particular output string. Introduced by Ray Solomonoff in the early 1960s, it sits at the intersection of computability theory and probability, providing a mathematically rigorous way to assign prior probabilities to hypotheses or data sequences based purely on their computational complexity. The measure is intimately connected to Kolmogorov complexity: outputs that can be produced by shorter programs receive higher probability, embodying a formal version of Occam's razor.

The mechanics rely on summing over all programs that produce a given output, weighting each by 2 raised to the negative power of its length in bits. This yields a probability distribution over all possible outputs — one that is universal in the sense that it dominates any other computable probability distribution up to a constant factor. Because of this dominance property, a predictor based on algorithmic probability will eventually outperform any computable prediction strategy, making it theoretically optimal for sequence prediction and inductive inference.

In machine learning, algorithmic probability underpins Solomonoff induction, a framework for predicting future observations given a finite history of data. The approach assigns higher credence to continuations that can be described by simpler programs, providing a principled basis for generalization. While the measure is not directly computable — it is only approximable from above — it serves as a gold standard against which practical learning algorithms can be benchmarked. Concepts like minimum description length (MDL) and Bayesian model selection can be understood as tractable approximations to the idealized Solomonoff prior.

Algorithmic probability matters to AI research because it offers a theory of learning that is both universal and formally grounded, free from arbitrary choices about model families or feature representations. It has influenced the development of AIXI, a theoretical model of general intelligence that uses Solomonoff induction as its prediction component, and continues to inform work on meta-learning, compression-based generalization bounds, and the foundations of statistical learning theory.