Temporal Complexity next up previous contents
Next: Fast Computation of Finite Up: No Title Previous: Between EOMs and GTMs?

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 PG and PE 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.''


Juergen Schmidhuber

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