en.wikipedia.org/wiki/Solomonoff%27s_theory_of_inductive_inference
2 corrections found
the best possible scientific model is the shortest algorithm that generates the empirical data under consideration.
Solomonoff induction does not pick a single shortest algorithm as the exact 'best model'. Its predictor is a weighted mixture over all programs consistent with the data, with shorter programs given more weight.
Full reasoning
This sentence collapses Solomonoff induction into a single shortest-program rule, but that is not how the theory is defined.
In Solomonoff induction, the universal prior/predictor is obtained by summing over all programs that can generate the observed data, weighting each program by an exponential penalty for length. Marcus Hutter’s textbook gives the construction explicitly: the probability of a string is obtained by summing 2^{-length(p)} over all programs p that output that string/prefix. That is a Bayesian mixture over many hypotheses, not selection of one shortest algorithm.
Ray Solomonoff’s own 1960 abstract also distinguishes the two ideas. He says the shortest input/program gives only an approximation to the a priori probability, and then says a more exact formulation follows. So the shortest program is at most a simplification or approximation related to Kolmogorov complexity/MDL, not the literal statement of Solomonoff induction itself.
So the article’s wording is inaccurate: Solomonoff induction formally weights all compatible computable hypotheses, rather than declaring that the exact best scientific model is simply the single shortest algorithm producing the data.
2 sources
- An Introduction to Universal Artificial Intelligence
Hutter defines the Solomonoff distribution by summing over all programs: “we sum over all programs p that output x*, weighted by … 2^{-ℓ(p)}” and then writes M(x) as a sum over those programs (pp. 175–176).
- Abstracts of Solomonoff Publications
In Solomonoff’s “A Preliminary Report on A General Theory Of Inductive Inference,” he writes: “An approximation to the apriori probability is given by the shortest input to the machine that will give the desired output. A more exact formulation is given …”
It is only "incomputable" in the benign sense that no scientific consensus is able to prove that the best current scientific theory is the best of all possible theories.
Here 'incomputable' is explained incorrectly. In Solomonoff induction, incomputability is a formal computability-theoretic result tied to the halting problem, not a matter of scientific consensus or proof standards.
Full reasoning
This sentence gives the wrong meaning of incomputable.
In Solomonoff induction, incomputability is a formal mathematical property: there is no algorithm that can compute the universal prior/predictor exactly in general. Hutter explains that the relevant Bayesian mixture is not computable because there is no computable enumeration of all computable probability measures, due to the halting problem; the Solomonoff prior is only lower semicomputable. That is a standard recursion-theoretic limitation.
Solomonoff likewise describes this as a property of the prediction method itself: in his abstract for “Does Algorithmic Probability Solve the Problem of Induction?”, he says that any device as accurate as algorithmic probability must necessarily be incomputable. Again, that is about what algorithms can compute, not about whether scientists can reach consensus on the best theory.
So the article’s sentence is not just loose wording; it substitutes a sociological/philosophical claim about scientific agreement for the actual technical reason Solomonoff induction is incomputable.
2 sources
- An Introduction to Universal Artificial Intelligence
Hutter states that the Solomonoff mixture “fails to be computable” because “there is no computable enumeration of all computable probability measures due to the Halting problem,” and notes that the predictor is only lower semicomputable (pp. 170, 173).
- Abstracts of Solomonoff Publications
In Solomonoff’s “Does Algorithmic Probability Solve the Problem of Induction?”, he writes: “any device as accurate as ALP must necessarily be incomputable.”