Proportion of valid programs view of Solomonoff induction

Proportion of valid programs view of Solomonoff induction is one of several ways of viewing the deterministic variant of Solomonoff induction. This view roughly says that to get the prior probability of seeing some output string $x$, one should take all programs in some relevant class and find the fraction of programs that output string $x$. For example, if we consider 500 programs in our class and 10 of them output $x$, the prior probability of seeing $x$ is 10/500 = 1/50.

This view is intuitive, assuming that one accepts the wikipedia:Principle of indifference. The idea is that one knows that the actual program is in the class, but one does not know which program. Since the programs represent mutually exclusive and collectively exhaustive possibilities, if there are $n$ programs the prior probability assigned to each program is $1/n$. If we want to know the prior probability of seeing the output $x$, we can just add up the probabilities of the programs that output $x$. If there are $m$ such programs, we end up with $m/n$.

The terminology "proportion of valid programs view" is not standard in the literature; this "view" does not seem to have a name (none of the other views seem to have a name either).

How to decide on the class of programs

• all programs of length equal to n? -- this assumption is natural if we assume there is some deterministic program "out there" that the world is running. Then it must have some length n, even though we don't know what that n is.
• all programs of length up to n?
• all programs?
• all programs with valid syntax?
• all programs that halt and produce some output?

See also

• Equivalence of random coinflips view and minimal programs view

External links

• "A Simple Heuristic Explanation of Solomonoff Induction"