Solomonoff induction

The Solomonoff induction is a formal theory of universal prediction developed by Ray Solomonoff in 1964. It defines a universal prior over all computable hypotheses, weighted by their inverse Kolmogorov complexity — simpler hypotheses receive higher prior probability. Given observed data, Solomonoff induction predicts future observations by averaging over all hypotheses weighted by this prior, normalized by how well each hypothesis explains the data seen so far.

The theory is provably optimal in a specific sense: no other computable prediction method can outperform it by more than a constant factor across all possible data sequences. But this optimality is purchased at a severe cost: the universal prior is uncomputable, requiring enumeration of all possible programs, and the framework assumes that the true data-generating process is itself computable — an assumption that cannot be verified from within the framework.

Solomonoff induction is the purest expression of Bayesian reasoning applied to induction. It makes explicit what most Bayesian frameworks leave implicit: that the choice of prior is not merely a matter of convenience but a commitment to a theory of what is computable. The universal prior is not a neutral starting point. It is a bet that the universe is computable — and that bet has no empirical justification, only a mathematical elegance.