Variants of Solomonoff induction

This page lists some variants of Solomonoff induction.

For determinism, I think "deterministic" is the same as "Solomonoff prior" and "stochastic" is the same as "universal mixture". Sterkenburg calls deterministic versions a "bottom-up approach" whereas the universal mixture is a "top-down approach" (p. 30). For deterministic variants, the type of universal machine must be specified. With universal mixtures, one must specify two things: the weighting to use, and the class of distributions to consider.

For discrete vs continuous, I think this just means whether the prior we define is over finite strings or over infinite sequences (where we want to know the probability of an infinite sequence starting with a given finite string).

Source	Formula	Determinism	Discrete vs continuous	Notes
LessWrong Wiki	$m(y_0)={\sum }_{p\in \mathcal{P}:U(p)=y_0}{2}^{-\ell (p)}$ where $\mathcal{P}$ is the set of self-delimiting programs	Deterministic; page doesn't say type of machine, but uses self-delimiting programs and it's discrete, so prefix Turing machine?	Discrete because of the $U(p)=y_0$ rather than $U(p)=y_0*$
Scholarpedia discrete universal a priori probability	$m(x)={\sum }_{p:U(p)=x}{2}^{-\ell (p)}$ where the sum is over halting programs	deterministic? prefix Turing machine	discrete
Scholarpedia continuous universal a priori probability	$M(x)={\sum }_{p:U(p)=x*}{2}^{-\ell (p)}$ where the sum is over minimal programs	deterministic? Monotone Turing machine	Continuous
Sterkenburg (p. 22)	$P_{\mathrm{I}}(\sigma )=\underset{n\to \mathrm{\infty }}{lim}\frac{\left|T_{\sigma ,n}\right|}{\left|T_n\right|}$ where $\sigma$ is a finite string, $T_n$ is the set of all halting (valid) inputs of length $n$ to the reference machine $U$, $T_{\sigma ,n}$ is the set of all halting (valid) inputs of length $n$ that output something starting with $\sigma$	deterministic; universal Turing machine (no restrictions on prefix-free-ness)	discrete?
Sterkenburg (p. 24)	$P{\text{'}}_{\mathrm{I}\mathrm{I}}(\sigma )=2^{-\left|{\tau }_{\mathrm{m}\mathrm{i}\mathrm{n}}\right|}$ where ${\tau }_{\mathrm{m}\mathrm{i}\mathrm{n}}$ is the shortest program $\tau$ such that $U(\tau )=\sigma$ (i.e. the shortest program that causes the reference machine to output $\sigma$ and halt)	deterministic; universal Turing machine, universal prefix machine (to get a probability distribution; see remark on p. 27)	discrete?	this formula does not define a probability distribution over strings $\sigma$ because the sum of probabilities does not converge
Sterkenburg (p. 25)	$P^{\prime }{\text{'}}_{\mathrm{I}\mathrm{I}}(\sigma )=\underset{n\to \mathrm{\infty }}{lim}{\sum }_{\tau \in T_{\sigma ,n}}{2}^{-\left|\tau \right|}$ where $T_{\sigma ,n}$ is the set of all programs $\tau$ of length $n$ such that $U(\tau )$ begins with $\sigma$	deterministic; universal Turing machine		$P^{\prime }{\text{'}}_{\mathrm{I}\mathrm{I}}(\sigma )$ is divergent even for a single $\sigma$, so this is not actually a workable version, but is intended as a stepping stone
Sterkenburg (p. 26)	$P_{\mathrm{I}\mathrm{I}}(\sigma )=\underset{ϵ\to 0}{lim}\underset{n\to \mathrm{\infty }}{lim}{\sum }_{\tau \in T_{\sigma ,n}}{(\frac{1-ϵ}{2})}^{\left|\tau \right|}$	deterministic; universal Turing machine, universal prefix machine (to get a probability distribution; see remark on p. 27)		The use of the $ϵ$ is a hack to get the sum to converge
Sterkenburg (p. 29)	$Q_U(\sigma )={\sum }_{\tau \in T_{\sigma }}{2}^{-\left|\tau \right|}$ where $T_{\sigma }$ is the set of minimal descriptions of $\sigma$ (i.e. set of programs that output something starting with $\sigma$ such that if one removes one bit from the end of the program, it no longer outputs something starting with $\sigma$)	deterministic; universal monotone machine	continuous?
Sterkenburg (p. 31)	$P_{\mathrm{I}\mathrm{V}}(\sigma )=\underset{n\to \mathrm{\infty }}{lim}{\sum }_i{f}_{i,n}{P}_i(\sigma )$	Stochastic;
Sterkenburg (p. 33)	${\xi }_w(\sigma )={\sum }_{i}w({\mu }_i){\mu }_i(\sigma )$	Stochastic; weighting unspecified, except for the requirement that $w({\mu }_i)>0$ for all $i$ and that ${\sum }_{i}w({\mu }_i)\le 1$; the model class is all semicomputable semimeasures