EOMs dominate MTMs

Similarly, some $x$ are compactly describable on EOMs but not on MTMs. To see this, consider Chaitin's $Omega$, the halting probability of an MTM whose input bits are obtained by tossing an unbiased coin whenever it requests a new bit [14]. $Omega$ is c.e. (dovetail over all programs $p$ and sum up the contributions $2^{-l(p)}$ of the halting $p$), but there is no recursive upper bound on the number of instructions required to compute $Omega_{n}$, given $n$. This implies $K(Omega_{n}) = n + O(1)$ [14] and also $K^M(Omega_{n}) = n + O(1)$. It is easy to see, however, that on nonhalting EOMs there are much more compact descriptions:

$$K^E(\Omega_{n}) \leq O(K(n)) \leq O(log n);$$ (9)

that is, there is no upper bound of

$$K^M(\Omega_{n}) - K^E(\Omega_{n}).$$ (10)