Enumerable Priors vs FAST next up previous contents
Next: Speed Prior S and Up: Temporal Complexity Previous: Speed-Based Characterization of the

Enumerable Priors vs FAST

The FAST algorithm gives rise to a natural prior measure on the computable objects which is much less dominant than $\mu^M$, $\mu^E$ and $\mu^G$. This prior will be introduced in Section 6.5 below. Here we first motivate it by evaluating drawbacks of the traditional, well-studied, enumerable prior $\mu^M$ [#!Solomonoff:64!#,#!Levin:74!#,#!Solomonoff:78!#,#!Gacs:83!#,#!LiVitanyi:97!#] in the context of FAST.

Definition 6.2 (tex2html_wrap_inline$p x, p _i x $)   Given program prefix p, write $p \to x$ if our MTM reads p and computes output starting with $x \in B^*$, while no prefix of p consisting of less than l(p) bits outputs x. Write $p \to_i x$ if $p \to x$ in PHASE i of FAST.

We observe that

\begin{displaymath}\mu^M(x) = lim_{i \to \infty} \sum_{p \to_i x} 2^{-l(p)},
\end{displaymath} (45)

but there is no recursive function i(x) such that

\begin{displaymath}\mu^M(x) = \sum_{p \to_{i(x)} x} 2^{-l(p)},
\end{displaymath} (46)

otherwise $\mu^M(x)$ would be recursive. Therefore we might argue that the use of prior $\mu^M$ is essentially equivalent to using a probabilistic version of FAST which randomly selects a phase according to a distribution assigning zero probability to any phase with recursively computable number. Since the time and space consumed by PHASE i is at least O(2i), we are approaching uncountable resources as i goes to infinity. From any reasonable computational perspective, however, the probability of a phase consuming more than countable resources clearly should be zero. This motivates the next subsection.


next up previous contents
Next: Speed Prior S and Up: Temporal Complexity Previous: Speed-Based Characterization of the
Juergen Schmidhuber
2001-01-09


Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI