Next: Which is the True'' Up: Expressiveness of EOMs and Previous: EOMs dominate MTMs

### GTMs dominate EOMs -- novel objects less regular than

We will now show that there are describable strings that are constructively computable in the limit and have a short GTM description yet are even more random'' than Chaitin's Omegas, in the sense that even on EOMs they do not have any compact descriptions -- contrast this with Kurtz's and Kucera's nonconstructive randomness in the arithmetic hierarchy [27,26].

Theorem 3.3   For all there are with

That is, is unbounded.

Proof. For and universal EOM define

 (11)

The reader should not worry about the sum over uncountably many objects, because the dyadic expansion of is EOM-computable or c.e. The algorithm works as follows:
Algorithm A: Initialize the real-valued variable by 0, run all possible programs of EOM dovetail style such that the -th step of the -th program is executed in the -th phase; whenever the output of a program prefix starts with some satisfying for the first time, set ; henceforth ignore continuations of .
approximates from below in c.e. fashion -- infinite are not worrisome as must only read a finite prefix of to observe if the latter holds indeed. We will now show that knowledge of , the first bits of , allows for constructing a bitstring with when has low complexity.

Suppose we know . Once algorithm A above yields we know that no programs with will contribute any more to V. Choose the shortest satisfying , where is the lexicographically smallest previously computed by algorithm A such that . Then cannot be among the strings T-describable with fewer than bits. Using the Invariance Theorem (compare Proposition 3.1) we obtain .

While prefixes of are greatly compressible on EOMs, is not. On the other hand, is compactly G-describable: . For instance, choosing a low-complexity , we have .

The above construction shows that the novel objects are just as computable in the limit'' as , despite being more random. An interesting topic of future research may be to identify the most random describable object, if there is one, which we doubt.

The discussion above also reveals a natural complexity hierarchy. Ignoring additive constants, we have

 (12)

where for each '' relation above there are which allow for replacing '' by .''

Next: Which is the True'' Up: Expressiveness of EOMs and Previous: EOMs dominate MTMs
Juergen Schmidhuber 2003-02-13