Solomonoff Induction

Solomonoff induction is the theoretically optimal method for prediction and inductive inference, combining the universal prior with Bayesian updating to produce predictions that converge to the truth faster than any computable alternative. Developed by Ray Solomonoff in 1964, it formalizes the intuition that simpler explanations are more probable by weighting hypotheses according to their algorithmic description length.

Given a sequence of observations, Solomonoff induction predicts the next symbol by averaging the predictions of all computable hypotheses, weighted by their posterior probabilities under the universal prior. The result is a predictor that dominates all others: its error rate is bounded above by a constant multiple of the error rate of any computable predictor, regardless of the data-generating process.

This optimality comes at a cost: Solomonoff induction is uncomputable. Evaluating all programs and determining which halt and produce the observed data requires solving the halting problem. The framework is therefore a boundary theorem — it establishes what any practical learning algorithm approximates, not a procedure that can be executed. Machine learning, minimum description length methods, and compression-based inference are all computable shadows of Solomonoff induction.