Algorithmic Probability

In the [YOU] on AI Field Guide

The cycle that began with [YOU] on AI finds in algorithmic probability the rigorous foundation beneath the slogan “compression is comprehension” that circulates through contemporary AI discourse. The slogan is usually stated informally; algorithmic probability is the proof that it is more than a metaphor. When a language model is trained to minimize prediction loss, it is—by a mathematical equivalence that Solomonoff established—finding the shortest sufficient description of its training data. That compression is what generalization is: finding a shorter description means finding a pattern that extends beyond the specific examples, rather than memorizing them. The systems that generalize best are the ones that have best approximated the task of finding short descriptions, which is the task that algorithmic probability defines precisely.

Algorithmic probability also clarifies the limits that the cycle keeps insisting on. The simplicity bias is the correct prior for learning from any data with computable structure, but it is the prior for finding the correct explanation of what has been seen—not for producing true statements about a world that may depart from the training data in ways the training data could not anticipate. A model that has found the shortest description of its training corpus has correctly approximated Solomonoff’s prescription and may still be wrong about the world, because the world is not the corpus. The mathematics certifies the quality of the induction, not the accuracy of the conclusion.

Origin

Solomonoff introduced the concept in his 1960 technical report and developed it formally in 1964. The construction required two ingredients that were separately available and had never been combined in this way: the theory of universal computation that Alan Turing had established in 1936, which gave a precise meaning to “all programs” and “program length”; and Bayesian probability theory, which provided the framework for turning a prior over programs into predictions about the next observation. Solomonoff also drew on the principle of multiple explanations, attributed to Epicurus, which says that all explanations consistent with the data should be retained rather than selecting one. The result—keep all explanations, weight them by simplicity—reconciled a tension two millennia old.

The quantity Solomonoff defined is now studied under several names: algorithmic probability, Solomonoff’s a priori probability, the universal prior, and (in a related form) Kolmogorov complexity. The last name has become dominant in the mathematical literature, though Solomonoff’s priority and his prediction-first motivation are now widely acknowledged. The modern field of algorithmic information theory, which studies these quantities and their properties, traces its founding to Solomonoff and Kolmogorov jointly, with Gregory Chaitin as a third major early contributor.

Key Ideas

Simplicity as a number. The algorithmic probability of an object is determined by its description length in the shortest program that produces it. This gives simplicity a precise, objective measure: not a preference or a feeling but a quantity you can, in principle, compute (though not always in practice). Two competing theories can be compared by their shortest-program lengths rather than by intuitive appeal or rhetorical force. The one with the shorter description gets the higher prior probability, automatically and without negotiation.

The universal prior. Treating algorithmic probability as a prior over hypotheses gives the universal prior: the single, principled starting belief that any learner should have before seeing evidence. It says: expect the data to have been generated by a simple process; assign high prior probability to hypotheses with short descriptions. This is Solomonoff induction’s starting point, and it is what makes the induction universal: the prior is not tailored to any particular domain but applies to any data from any source.

The simplicity bias inside machine learning. The universal prior is the simplicity bias that lives, usually unacknowledged, inside every successful machine learning system. When engineers add regularization penalties for large weights, prefer smaller architectures that perform as well as larger ones, or observe that gradient descent tends to find broad solutions rather than narrow memorizing ones, they are implementing homemade approximations of the universal prior. None of these techniques is algorithmic probability; each is a computable gesture in its direction. Solomonoff’s theory tells us what all these scattered practices are approximations of and why they work.

The reference-machine caveat. Algorithmic probability depends on the choice of reference universal computer: different machines measure program lengths differently, shifting the prior by a bounded but nonzero amount. The saving grace is that any two universal machines can simulate each other with a fixed-size translation program, so the difference in measured complexity is at most a constant that washes out for long sequences. The universal prior is universal up to a constant, not in some machine-free absolute sense. This limit is important enough to state plainly: the theory is universal in the sense that it applies to all data and all domains, not in the sense that it yields a unique number independent of all representational choices.