Temporal Complexity

So far we have completely ignored the time necessary to compute objects
from programs.
In fact, the objects that are highly probable
according to *P*^{G} and *P*^{E} 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.''

- Fast Computation of Finite and Infinite Strings
- FAST: The Most Efficient Way of Computing Everything
- Speed-Based Characterization of the Describable
- Enumerable Priors vs FAST
- Speed Prior
*S*and Algorithm GUESS - Speed Prior-Based Inductive Inference
- Practical Applications of Algorithm GUESS

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