GTMs More Expressive Than EOMs -- Objects Less Regular Than $\Omega$

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 $z \in B^*$ with

$$K^E(z) > n - O(1),~~yet~~ K^G(z) \leq O(log~n).$$

That is, K^E(z) - K^G(z) is unbounded.  

Proof. For $x \in B^* \backslash \{ \lambda \}$ and universal EOM T define

$$\Xi(x) = \sum_{y \in B^{\sharp}: 0.y > 0.x} ~~ \sum_{p: T(p) \leadsto y} 2^{-l(p)}.$$ (13)

First note that the dyadic expansion of $\Xi(x)$ 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 $\Xi(x)$ 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 $\Xi(x)_n$, the first n bits of $\Xi(x)$, allows for constructing a bitstring z with $K^E(z) \geq n - O(1)$ when x has low complexity.

Suppose we know $\Xi(x)_n$. Once algorithm A above yields $V > \Xi(x)_n$ 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 $K^E(z) \geq n - O(1)$.

While prefixes of $\Omega$ are greatly compressible on EOMs, z is not. On the other hand, z is compactly G-describable: $K^G(z) \leq K(x) + K(n) + O(1)$. For instance, choosing a low-complexity x, we have $K^G(z) \leq O(K(n)) \leq O(log~n)$. $\Box$

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

$$K^G(x) \leq K^E(x) \leq K^M(x),$$ (14)

where for each ``$\leq$'' relation above there are x which allow for replacing ``$\leq$'' by ``<.''

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