A prior made from descriptions

Solomonoff begins with a long sequence T drawn from a finite alphabet. The sequence is the corpus, and it must contain all information allowed to influence the induction. For a candidate continuation a, the task is to assign something with the role of P(a|T). This formulation is intentionally broad. Measurements, words or images can be encoded as symbols, although the encoding choice will later reappear as a genuine boundary.

A machine M maps binary inputs to output strings. When M(s)=x, input s is a description of x relative to M. A universal machine can simulate any other machine: for each machine N, there is a fixed translator string c such that M(cs)=N(s) for every input s. The translator may be costly, but its length does not grow with the particular data.

The elementary weight is 2^{-|s|}, where |s| is the number of programme bits. Adding one bit halves the weight. Ten extra bits divide it by 1,024. This exponential schedule is not decorative. It is what random binary input supplies: a specified prefix of length n occurs with probability 2^{-n}. It also echoes ideal coding, in which probable objects deserve short codewords.

Why count more than the shortest programme? Suppose one output has a four-bit description and two independent six-bit descriptions. Their combined illustrative mass is 2⁻⁴+2⁻⁶+2⁻⁶=0.09375. A rival with one five-bit description has mass 0.03125. The first output wins not solely because its best description is shorter, but because all its descriptions add evidence. The arithmetic joins economy with multiplicity of possible causes.

Why compression can act as a prior

A prior ranks possibilities before the current evidence is used. Description length supplies such a ranking because a programme is a generative commitment. It must say enough to reproduce the observed regularity and, in a prediction setting, to continue producing symbols. A literal table pays for each irregular detail. A compact rule pays for reusable structure. The shorter code is not declared true; it is allowed to begin with more probability mass.

That distinction separates Solomonoff’s move from ordinary data compression. A compressor may care only about reproducing a completed file. An inductive description must also define a distribution over continuations or an output process that continues beyond the observed boundary. Two programmes can compress the prefix equally yet disagree about what follows. Their predictive probabilities remain separate until later evidence distinguishes them.

Solomonoff invokes Huffman coding as an inversion. Given a known distribution, Huffman’s construction gives short codewords to probable messages. Universal induction starts from available descriptions and reads shortness as evidence of prior probability. The inversion is a rationale rather than a theorem identifying every shortest programme with a uniquely correct probability. Code design normally starts with a distribution; Solomonoff is trying to construct one when no trusted distribution has been supplied.

“Many descriptions” adds a second source of mass. One regularity might be generated as an arithmetic formula, a small automaton or a compressed table. If these are genuinely distinct programme regions, their weights add. This prevents the outcome from depending solely on a fragile contest between two shortest strings. It also creates a technical responsibility: programme sets must be arranged so their binary cylinders can be weighted without double-counting arbitrary extensions.

The prior and the evidence play different roles. A short programme that predicts the data poorly loses through likelihood. A long programme that predicts each new symbol much better can eventually overcome its initial penalty. This is why simplicity bias does not license permanent loyalty to the simplest current story. The bias determines how much evidence a more complicated rival must earn before it takes control of the predictive mixture.

Four routes to the same summit, perhaps

Solomonoff’s first model sums weighted descriptions of Ta and of all its possible longer continuations, then normalises against descriptions of continuations of T. Its published expression uses nested limits and a factor (1−ε)/2 to control divergence. The underlying intuition is easier than the notation: a continuation deserves mass when short programmes can print it, especially when those programmes keep producing simple futures beyond it.

The “keep producing” clause matters. The partial string abcdabcdabcdabcdab becomes more economical if continued by cdabcd…, because the repeating unit closes. A programme that generates an indefinitely coherent extension can support the current prefix more strongly than one that stops at an awkward boundary. Solomonoff therefore treats possible futures as part of the evidence about how economically the prefix can be generated.

He also records three problems immediately. Non-halting programmes cannot be separated from halting ones by a general effective procedure. The required limits had not been proved to exist. The resulting value might depend critically on the chosen universal machine. These are not later objections pasted onto the paper. They are part of its original architecture.

The first equation is historically important precisely because it is awkward. For each extension length n, Solomonoff considers every n-symbol continuation after Ta, and then every finite description of those extended strings. A description of length N is weighted by [(1−ε)/2]^N. The denominator performs the analogous sum across continuations of T, making the ratio conditional. One limit sends the future horizon outward; another lets the damping parameter approach zero.

If the damping is removed from an isolated sum, the number of long descriptions can grow fast enough to make the expression diverge. Solomonoff inserted ε so descriptions much longer than roughly 1/ε contribute negligibly before the ratio limit is taken. A later author’s note attached to the TeX source warns that the ε limit belongs to the numerator-denominator ratio, not to the numerator alone. The warning reinforces the paper’s provisional status rather than altering its central weighting idea.

For practical calculation he proposes restricting attention to inputs that complete their output within a time limit τ. That makes the relevant sums finite. Increasing τ provides a sequence of approximations, though the paper does not claim a single useful approximation for every problem. Different applications in Part II use different simplifications. The proposal already contains the modern tension between a universal mathematical target and resource-bounded search.

The second model replaces terminating descriptions with a three-tape universal machine. Random bits arrive on a one-way input tape; the machine uses expandable working memory and writes symbols irreversibly on an output tape. An infinite output is meaningful when each symbol appears after finite computation. A minimal code for prefix T is an input segment just long enough to make the machine print T. Because these minimal input cylinders do not overlap, their 2^{-|s|} masses stay bounded.

In this second formulation the probability of continuation a is a ratio: sum the masses of minimal codes whose outputs begin with Ta, then divide by the corresponding mass for T. In modern shorthand, with qualifications about machine type and semimeasures, readers often encounter M(a|T)=M(Ta)/M(T). That compact notation expresses the conditioning move. It should not be mistaken for the exact historical notation or for an ordinary computable probability measure.

A minimal input code stops at the first point where the required output prefix has become inevitable. Remove its final input bit and it no longer forces that prefix. Such minimal codes are prefix-incomparable for the same event: one cannot be a proper prefix of another minimal code that already guarantees the same output. Their random-input cylinders can therefore be added without exceeding total mass. This is the geometric reason the second model avoids the explicit damping device used by the first.

Some random programmes never produce another symbol. Their mass does not necessarily flow to either next-symbol continuation. Modern treatments therefore call the induced object a semimeasure before normalisation: the mass of a prefix can exceed the sum assigned to its one-symbol extensions because computation may stall. Normalising changes computability properties and must be stated. Treating the missing mass as if it were an ordinary third outcome would describe a different predictive object.

The third model fixes a very large input length R. Give every R-bit input equal prior probability. Count how many meaningful inputs make the universal machine output a string beginning with T, and how many begin with Ta. Their ratio N_{Ta}/N_T estimates the conditional probability as R grows. This is a computational rendering of insufficient reason at the level of programmes, not at the level of outcomes.

The distinction is decisive. Outcomes with many programme causes occupy more of the input cube. Outcomes with a short causal prefix also own every longer input extending that prefix, subject to the machine convention. Equal weight over programmes therefore produces unequal weight over outputs. The prior is biased towards outputs with compressible generative structure without directly writing “prefer simple strings” into an outcome table.

The fixed-length view also makes the limiting move visible. At a small R, only programmes that fit inside the cube can contribute. Expanding R adds descriptions and extensions in exact powers of two. If the ratios stabilise, the count approaches the random-input interpretation. Yet finite counts can swing when a newly admitted short interpreter opens a large family of programmes. “Let R approach infinity” specifies an ideal construction, not a licence to ignore truncation effects in an executable version.

The fourth model changes vantage point. A probability evaluation method, or PEM, assigns prior probabilities to strings. Imagine every describable normalised PEM: a coin model, a Markov model, a grammar, a physical simulator and indefinitely many more. Give each method an a priori weight fᵢ related to description length. After observing T, multiply by the probability Pᵢ(T) that method gave the data. The prediction is the normalised weighted average of their continuation probabilities.

This is Bayesian model averaging with an enormous computable-model class. Short methods start ahead; methods that predicted the evidence well gain posterior weight. A longer model can overtake a short one if its likelihood advantage compounds across enough data. A short model is therefore preferred, not protected. Solomonoff’s stated goodness comparison uses the probability a method assigned to the observed string, and his argument for the mixture’s dominance is informal.

A normalised PEM obeys two conservation rules. The probabilities of all one-symbol extensions of a string must add to the probability of the string, and probabilities across the first symbol must add to one. These conditions let Bayes’s theorem convert prior string probabilities into continuation probabilities. A binary description of the method makes the chosen universal machine print successive bits of the method’s probability evaluations for requested strings.

The quantity fᵢ measures the asymptotic fraction of long binary strings that describe method Qᵢ. Its prior influence is then combined with Pᵢ(T), its assigned probability for the observed corpus. Equation 14 rewrites the construction as an explicit weighted vote. The vote of method i is its own conditional prediction multiplied by its posterior share. This form makes the Bayesian structure easier to see than the surrounding machinery.

Why might the mixture compete with any component? Suppose one method gives the realised data systematically higher probability than another. Their likelihood ratio can grow exponentially with sequence length, while the prior description weights remain fixed. Eventually predictive fit can dominate a finite prior disadvantage. The mixture retains the better method’s contribution throughout, so its cumulative performance can track that component up to a complexity cost. Part I presents this as plausibility under a stated goodness criterion, not as the later general loss-bound theorem.

There is also a self-reference wrinkle. Solomonoff says the combined method is not effectively computable and therefore does not include itself among the effectively describable evaluators being summed. The universal mixture is defined from computable components while its total evaluation exceeds what any one computable component can generally deliver. This is not a contradiction. It is another sign that the construction specifies an ideal probability assignment rather than a programme ready to run.

What Part II tests, and what it cannot certify

The second half of Solomonoff’s publication applies the ideas to Bernoulli prediction, a Markov-style source and phrase-structure grammar induction. The Bernoulli treatment reaches Laplace’s rule of succession under its approximations. The other examples become progressively less exact. Their value is diagnostic: can one general description-weighting idea recover intuitively plausible results across different forms of regularity?

Application success cannot retroactively prove every limit or equivalence asserted in Part I. Solomonoff says as much. The route from the basic equations to usable answers introduces approximations, so agreement with intuition imperfectly corroborates the foundations. Conversely, one poor approximation would not by itself refute the universal weighting principle. The model, approximation and application must be kept in separate evidential columns.

A finite bench for an infinite ideal

The universal mixture cannot be executed exactly. A programme may run forever without revealing whether it will eventually print the needed symbol. Any complete search for all descriptions inherits the halting problem. A demonstration must therefore announce its truncation instead of calling a small model library “Solomonoff induction”. The bench below contains eight hand-built predictors and a programme-length budget. It reveals the mechanism that survives approximation: exponential prior weights, likelihood updating and posterior averaging.

Each predictor has a code length and a next-bit probability. Deterministic rules are softened to 0.98 rather than one, so one mismatch does not annihilate them. The fair, quarter-bias and three-quarter-bias models use fixed Bernoulli likelihoods. A literal model stores the observed prefix at a code cost that grows with the data and then predicts evenly. The “language bonus” slider shortens only the alternating rule, simulating a reference language in which alternation is more primitive.

The approximation exposes a resource frontier. Increasing the programme budget admits more hypotheses and can move the prediction. Increasing runtime would reveal outputs from slow programmes and could move it again. There is no computable stopping certificate saying the omitted mass cannot matter. In practice, search strategies, domain languages and compute limits are part of the inductive system, not neutral implementation details outside it.

The literal-prefix model in the bench is deliberately revealing. It can fit any finite data by storing the observations, but its description grows one bit whenever the corpus grows. A reusable law pays a fixed programme cost and then generates more data cheaply. Early in a sequence, literal storage may remain competitive. As a stable pattern repeats, the reusable description’s likelihood advantage and fixed cost allow it to dominate. This is the point at which compression becomes predictive rather than retrospective.

Noise models show why an exact deterministic rule should not always receive probability one. If alternation is treated as perfect, one anomalous bit reduces its likelihood to zero and it never returns. A stochastic variant says alternation usually holds but errors occur with small probability. It survives a mistake, pays for its error parameter and can recover if later observations resume the pattern. Universal mixtures contain both exact and noisy explanations when their descriptions are computable.

A finite library also reveals model duplication. Writing the same predictor under ten names should not automatically multiply its epistemic support. In a true programme mixture, different descriptions genuinely contribute random-input mass, so representational redundancy is part of the reference machine. In a hand-built ensemble, careless duplication can arbitrarily skew results. Practical approximations need a coding convention, not merely a spreadsheet of candidate models.

What universality earns, and what it leaves unpaid

The most attractive claim is that a universal mixture need not know the true computable data-generating process in advance. If that process has some finite description, its contribution is included. A Bayesian mixture that assigns it positive prior mass can learn from accumulating evidence. Later theory gave rigorous convergence and loss bounds under specified computable-environment conditions. These results are central to modern Solomonoff induction, but they should not be projected backwards as proofs contained in Part I.

Part I’s machine-independence argument is more cautious. If U can simulate V with a fixed translator, U’s shortest code cannot be more than that translator length worse than V’s corresponding code. Solomonoff suggests that, for a very long redundant corpus and machines efficient for its regularities, such constant factors may approximately cancel in conditional probabilities. He lists the assumptions and calls the reasoning heuristic.

The additive invariance result is powerful for asymptotic complexity classes. It is weak protection for a short decision with high stakes. A translator penalty of 500 bits multiplies prior mass by 2⁻⁵⁰⁰. Enough likelihood can overcome it, but “enough” may be far beyond the available evidence. A theorem that constants vanish in a limit does not select a harmless finite reference language.

Machine choice can encode a substantive worldview. A language with concise arithmetic primitives favours numerical regularities. One with compact spatial transforms favours geometric structure. A language containing a special opcode for a particular dataset favours that dataset for an artificial reason. Universality guarantees simulation, but it does not distinguish a scientifically useful basis from a contrived one. Proposals for natural machines or coding conventions must add criteria beyond bare universality.

Non-computability produces a second boundary. Solomonoff explicitly conjectures that his expression is not effectively computable and proposes time-bounded approximations. Later work distinguishes lower semicomputability, normalisation and limit computability more carefully. The practical temptation is to say that a computable approximation inherits the ideal’s universality. That does not follow. An approximation can change which hypotheses receive positive mass or how machine dependence behaves.

Sven Neth sharpens the tension. One reply to reference-machine relativity appeals to different universal priors converging with more data. One reply to non-computability appeals to usable computable approximations. Yet computable approximations need not retain the universal convergence property that made the first reply attractive. The dilemma does not make the ideal mathematically empty. It prices claims that the ideal uniquely guides finite scientific or machine inference.

Convergence itself has conditions. The data-generating probability must lie within the relevant computable class, and the statement is normally probabilistic or cumulative rather than a guarantee that every next prediction improves monotonically. A predictor can be wrong at scattered times, learn slowly when the true process has a long description, or face sequences with negligible probability under the assumed source. “Universal” names the breadth of the computable class and dominance property, not immunity to every adversarial presentation.

The prior’s uncomputability also blocks a simple empirical comparison with ordinary predictors. One cannot run the exact ideal on a benchmark and read off its score. Comparisons use time-bounded searches, restricted model classes, compression algorithms or other proxies. Those systems may be valuable, but their empirical results support the proxy and its engineering choices. They do not constitute a direct experiment on the inaccessible mathematical mixture.

Representation is a third boundary. Solomonoff asks that the corpus contain all information used in prediction. Encoding a laboratory record into a symbol string decides temporal order, precision, missingness and what counts as one symbol. Two lossless computable encodings are related in principle, but their finite description costs and the convenience of regularities can differ. A lossy encoding can erase the very dependence one hopes to learn.

Order is particularly consequential. If a table is serialised row by row, nearby symbols represent different relations than if it is serialised column by column. A universal machine can in principle discover a transposition, but doing so incurs a description cost. Metadata that states the schema can shorten the useful model dramatically. The instruction that T contain all relevant information therefore includes the rules by which raw observations became a sequence.

Solomonoff probability is not simply Kolmogorov complexity

The next canon paper will distinguish three quantitative approaches to information. Kolmogorov complexity asks for the length of a shortest programme producing an individual object. Solomonoff probability sums the weights of programmes producing an output prefix and then uses conditional ratios for prediction. The coding theorem later links negative logarithmic universal probability and prefix complexity up to additive terms, but the objects and questions remain distinct.

A shortest-description approximation can be useful when one programme dominates the sum. It can fail when many slightly longer programmes collectively carry substantial mass. Conversely, knowing the total algorithmic probability does not identify the shortest explanatory mechanism. Compression, probability and prediction reinforce one another without becoming synonyms.

The same boundary protects concepts further along this canon. Accurate sequence prediction is a component of intelligence under many definitions. It is not equivalent to agency because goals, actions and counterfactual consequences are absent. It is not understanding because success may be assessed entirely at the output distribution. It is not consciousness or sentience because no bridge connects predictive probability to experience. The paper changes how hypotheses are weighted; it does not settle what sort of system has a point of view.

Its enduring thesis is narrower and stronger. When the hypothesis class is uncertain, preserve a mixture over every describable candidate, give concise candidates more initial mass, and let predictive evidence redistribute that mass. Any practical descendant must declare what it substituted for “every”, which description language it privileged, how much computation it spent and which data boundary it treated as the world.

Memory studio: recover the mixture, then its receipt

Place in the canon

Paper 0005 sits in Stage S0, Module S0M1: Computability, algorithms and information theory. Church and Turing supply the boundary and the universal machine. Shannon supplies the probability-coding relation, while Huffman supplies the inverse-coding intuition Solomonoff explicitly invokes. The new capability is a general prior over computable descriptions joined to Bayesian prediction.

The next three papers separate ideas that Solomonoff brought together. Kolmogorov’s 1965 “Three Approaches to the Quantitative Definition of Information” sharpens individual-object description complexity. Chaitin’s 1966 “On the Length of Programs for Computing Finite Binary Sequences” develops programme-size complexity and its invariance. Cook’s 1971 “The Complexity of Theorem-Proving Procedures” changes the question from what is computable to how resource cost structures feasible computation.

Read forward with one distinction intact. A short programme can support a high prior without being fast. A programme can be fast without being short. A predictor can be accurate without choosing actions. An agent can choose actions without possessing experience. The canon will reuse all four separations.

The universal prior is an ideal with an audit trail

Solomonoff’s decisive step was to refuse the forced choice between one favoured model and an unstructured list of alternatives. Every computable explanation gets a place in the mixture. Concision determines its starting influence; agreement with evidence determines how that influence changes. The next symbol is predicted by pooled surviving mass.

The price is visible in the construction. The universal sum cannot be computed exactly. Description length is relative to a universal machine. Finite approximations inherit choices about language, time, programme budget and data encoding. Part I knew much of this and did not hide it behind later success. Its own restraint is part of the lesson.

A mature use of algorithmic probability therefore makes two statements together. First: a general predictor should reward explanations that compress the evidence and should average rather than prematurely eliminate compatible causes. Second: any executable system is a bounded descendant whose omissions may change the answer. The theory is most useful when both statements travel as one.

Continue through the canon