Close Approximation of the Speed Prior

The precise value of $S(x)$ is only computable in the limit. However, within finite time we can compute $S(x)$ with arbitrary precision. There is a halting algorithm AS that takes as input $x$ and some $\epsilon > 0$, and outputs an approximation $\bar{S}_{\epsilon}(x)$ such that

$$\mid \bar{S}_{\epsilon}(x) - S(x) \mid < \epsilon S(x).$$ (6)

AS works as follows:

Algorithm AS:

1. Run FAST until $x$ is computed for the first time in PHASE $Kt(x)$. Let $n(x)$ denote the size of the smallest program for $x$ found in this PHASE.

3. Set $\bar{S}_{\epsilon}(x)$ equal to the sum of the contributions to $S(x)$ of all programs of all PHASEs up to the PHASE with number

$$Kt(x) + n(x) + 1 - \log \epsilon.$$

AS halts after step 3 since any additional PHASEs are superfluous in the following sense: even if all their programs computed $x$, their cumulative contributions to $S(x)$ could not exceed $\epsilon S(x)$.

Back to Speed Prior page