Enumerable Priors vs FAST
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 , and . 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 [#!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 if our MTM reads p and computes output starting with , while no prefix of p consisting of less than l(p) bits outputs x. Write if in PHASE i of FAST.

We observe that

 (45)

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

 (46)

otherwise would be recursive. Therefore we might argue that the use of prior 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: 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