Speed Prior-Based Inductive Inference

Given $S$, as we observe an initial segment $x \in B^*$ of some string, which is the most likely continuation? According to Bayes,

$$S(xy \mid x) = \frac{S(x \mid xy) S(xy)} {S(x)} = \frac{S(xy)} {S(x)},$$ (5)

where $S(z^2 \mid z^1)$ is the measure of $z^2$, given $z^1$. Having observed $x$ we will predict those $y$ that maximize $S(xy \mid x)$. Which are those? In what follows, we will confirm the intuition that for $n \rightarrow \infty$ the only probable continuations of $x_{n}$ are those with fast programs. The sheer number of ``slowly'' computable strings cannot balance the speed advantage of ``more quickly'' computable strings with equal beginnings.

Proof. Since no program that requires at least $g(n)$ steps for producing $x_n$ can compute $x_n$ in a PHASE with number $< \log~g(n)$, we have

$$Q(x,g,f) \leq \lim_{n \to \infty} \frac {\sum_{i=1}^{\infty... ... \sum_{p \stackrel{= f(n)}{\longrightarrow_i} x_n}2^{-l(p)}}$$

$$\leq \lim_{n \to \infty} \frac{ f(n) \sum_{p \to x_n} 2^{-l... ...ty} \frac{ f(n) } { g(n) } \frac{ 1 } { 2^{-l(p^x)} } = 0.$$

Here we have used the Kraft inequality [13] to obtain a rough upper bound for the enumerator: when no $p$ is prefix of another one, then $\sum_{p} 2^{-l(p)} \leq 1.$ Q.E.D.

Hence, if we know a rather fast finite program $p^x$ for $x$, then Theorem 1 allows for predicting: if we observe some $x_n$ ($n$ sufficiently large) then it is very unlikely that it was produced by an $x$-computing algorithm much slower than $p^x$.

Among the fastest algorithms for $x$ is FAST itself, which is at least as fast as $p^x$, save for a constant factor. It outputs $x_n$ after $O(2^{Kt(x_n)})$ steps.

Back to Speed Prior page