**Solomonoff induction **is an inference system defined by Ray Solomonoff~~ defined an inference system~~ that will learn to correctly predict any computable sequence with only the absolute minimum amount of data. This system, in a certain sense, is the perfect universal prediction algorithm.

More precisely, suppose that a particular infinite input string *x*_{0} is about to be fed into *U*. However, you know nothing about *x*_{0} other than that each term of the string is either 0 or ~~1~~~~.~~1. As far as your state of knowledge is concerned, the *i*th digit of *x*_{0} is as likely to be 0 as it is to be ~~1~~~~,~~1, for all *i* = 1, 2, ~~…~~~~.~~…. You want to find the *a priori* probability *m*(*y*_{0}) of the following proposition:

Unfortunately, computing the exact value of *m*(*y*_{0}) would require solving the halting problem, which is undecidable. Nonetheless, it is easy to derive an expression for *m*(*y*_{0}). If *U* halts on an infinite input string *x*, then *U* must read only a finite initial segment of *x*, after which *U* immediately halts. We call a finite string *p* a *self-delimiting program* if and only if there exists an infinite input string *x* beginning with *p* such that *U* halts on *x* immediately after reading to the end of *p*. The set ~~𝒫~~𝒫 of self-delimiting programs is the *prefix code* for *U*. It is the determination of the elements of ~~𝒫~~𝒫 that requires a solution to the halting problem.

Given *p* ∈ 𝒫, we write ~~"~~~~prog~~"prog (*x*_{0}) = *p*" to express the proposition that *x*_{0} begins with *p*, and we write "*U*(*p*) = *y*_{0}" to express the proposition that *U* produces output *y*_{0}, and then halts, when fed any input beginning with *p*. Proposition (*) is then equivalent to the exclusive disjunction

⋁_{p}_{ ∈ 𝒫: }_{U}_{(}_{p}_{) = }_{y}_{0}(prog (*x*_{0}) = *p*).

Since *x*_{0} was chosen at random from ~~{0,~~{0, 1}^{ω}, we take the probability of prog (*x*_{0}) = *p* to be 2^{ − ℓ(}^{p}^{)}, where ~~ℓ(~~*ℓ(**p*) is the length of *p* as a bit string. Hence, the probability of (*) is

*m*(*y*_{0}) := ∑_{p}_{ ∈ 𝒫: }_{U}_{(}_{p}_{) = }_{y}_{0}2^{ − ℓ(}^{p}^{)}.

~~Blog posts~~