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].

**Proof.** For
and universal
EOM define

(11) |

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