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.