Why Simplicity Is a Good Prior A Computational Explanation of Solomonoff Induction

Occam's Razor is not a heuristic — it is the mathematically forced consequence of treating hypotheses as programs on a universal computer.

The core idea is disarmingly simple. Imagine feeding random coin flips into a computer. The computer reads bits until it hits a valid program and halts. A 10-bit program appears with probability 2⁻¹⁰; a 110-bit program appears with probability 2⁻¹¹⁰. That's a factor of 2¹⁰⁰ difference — purely from combinatorics. If you're agnostic about which program generated your data, this exponential gap is your prior. Short programs are just astronomically more likely to be drawn at random. This is Solomonoff's prior, and the paper's main job is to show it's not merely reasonable but provably optimal.

The technical machinery that makes this rigorous is the "prefix-free" constraint on programs. A set of programs is prefix-free if no valid program is a prefix of another — once the machine reads enough bits to halt, it stops, and the trailing bits don't count. This means many syntactically long bitstrings are really just short programs with ignored tails. Kraft's inequality then guarantees the program lengths define a proper probability distribution. The resulting object, M(x), is the sum of 2⁻|p| over all programs p that produce output starting with x. It's called a semimeasure (sums to ≤1) because some programs loop forever.

Why is M a good prior, not just a prior? The dominance theorem answers this. For any computable environment μ — any stochastic process that can be described by a program — M never undershoots μ by more than a constant factor: M(x) ≥ c_μ · μ(x), where c_μ ≈ 2^{-K(μ)} and K(μ) is the length of the shortest program describing μ. The practical consequence is a regret bound: a predictor using M accumulates at most O(K(μ)) extra bits of log-loss compared to an oracle that knows μ exactly, and this gap is fixed — it doesn't grow with the amount of data. Per-symbol error goes to zero. You pay a one-time "complexity tax" equal to the description length of the truth, then you're essentially optimal forever after.

The paper also closes the loop to Minimum Description Length (MDL). The coding theorem says K(x) ≈ -log₂ M(x): strings that are probable under M are exactly the strings that compress well. This means maximizing the Bayesian posterior P(H|D) under a Solomonoff prior is mathematically identical to minimizing K(H) - log P(D|H) — model complexity plus fit error. Occam's Razor and data compression are the same thing, stated in different languages. One important caveat the paper is careful to flag: computability alone doesn't guarantee the world is simple. If K(μ) is astronomically large, the regret bound is too loose to be useful at any finite data scale. The framework only delivers practical guarantees if the true environment has moderate algorithmic complexity — which is an empirical bet about our actual universe, not a theorem.