GTMs More Expressive Than EOMs -- Objects Less Regular Than    Next: Measures and Probability Distributions Up: Expressiveness of EOMs and Previous: EOMs More Expressive Than

### GTMs More Expressive Than EOMs -- Objects Less Regular Than 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.

Theorem 3.3   For all n there are with That is, KE(z) - KG(z) is unbounded.

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 variable V by 0, run all possible programs of EOM T dovetail style such that the n-th step of the i-th program is executed in the n+i-th phase; whenever the output of a program prefix q starts with some y satisfying 0.y > 0.x for the first time, set V:= V+ 2-l(q); henceforth ignore continuations of q.
V approximates from below in enumerable fashion -- infinite p are not worrisome as T must only read a finite prefix of p to observe 0.y > 0.x if the latter holds indeed. We will now show that knowledge of , the first n bits of , allows for constructing a bitstring z with when x has low complexity.

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.ymin - 0.x)/2, where ymin 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 (14)

where for each '' relation above there are x which allow for replacing '' by <.''    Next: Measures and Probability Distributions Up: Expressiveness of EOMs and Previous: EOMs More Expressive Than
Juergen Schmidhuber
2001-01-09

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