The FAST algorithm gives rise to a natural prior
measure on the computable objects which is much less
dominant than ,
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
in the context of FAST.
Definition 6.2 (tex2html_wrap_inline$p x, p _i x $)
Given program prefix p, write
our MTM reads p and computes output starting with ,
while no prefix of p consisting of less than l(p) bits
outputs x. Write
in PHASE i of FAST.
We observe that
but there is no recursive function i(x) such that
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.