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 $\mu^E$ introduced in the previous sections yet quite improbable according to less dominant priors studied earlier (such as $\mu^M$ 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 $\Omega_{n}$ 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.''

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