We will now show that there are describable strings that 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.

**Proof.** For
and universal
EOM *T* define

(13) |

First note that the dyadic expansion of is EOM-computable or enumerable. The algorithm works as follows:

Algorithm A: Initialize the real-valued variableVby 0, run all possible programs of EOMTdovetail style such that then-th step of thei-th program is executed in then+i-th phase; whenever the output of a program prefixqstarts with someysatisfying 0.y> 0.xfor the first time, setV:=V+ 2^{-l(q)}; henceforth ignore continuations ofq.

Suppose we know .
Once algorithm A above yields
we know that no programs *p* with *l*(*p*) < *n* will contribute
any more to V. Choose the shortest *z* satisfying
0.*z* = (0.*y*_{min} - 0.*x*)/2,
where *y*_{min} is the lexicographically smallest
*y* previously computed by algorithm A
such that 0.*y* > 0.*x*. Then *z* cannot be among the strings T-describable
with fewer than *n* bits. Using the Invariance Theorem
(compare Def. 3.3)
we obtain
.

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

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

where for each ``'' relation above there are

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