So far we have completely ignored the time necessary to compute objects
from programs.
In fact, the objects that are highly probable
according to PG and PE and
introduced in the previous sections yet
quite improbable according to less dominant priors studied earlier (such
as
and recursive
priors [#!Zvonkin:70!#,#!Levin:74!#,#!Solomonoff:78!#,#!Gacs:83!#,#!LiVitanyi:97!#])
are precisely those whose computation
requires immense time. For instance, the
time needed to compute
the describable, even enumerable
grows faster than any recursive function of n, as shown by Chaitin
[#!Chaitin:87!#].
Analogue statements hold for the z of Theorem 3.2.
Similarly, many of the semimeasures discussed above
are approximable, but the approximation process
is excessively time-consuming.
Now we will study the opposite extreme, namely, priors with a bias towards the fastest way of producing certain outputs. Without loss of generality, we will focus on computations on a universal MTM. For simplicity let us extend the binary alphabet such that it contains an additional output symbol ``blank.''