EOMs More Expressive Than MTMs next up previous contents
Next: GTMs More Expressive Than Up: Expressiveness of EOMs and Previous: Expressiveness of EOMs and

EOMs More Expressive Than 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 [#!Chaitin:87!#]. $\Omega$ is enumerable (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)$ [#!Chaitin:87!#] 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:

\begin{displaymath}K^E(\Omega_{n}) \leq O(K(n)) \leq O(log~n);
\end{displaymath} (11)

that is, there is no upper bound of

 \begin{displaymath}K^M(\Omega_{n}) - K^E(\Omega_{n}).
\end{displaymath} (12)



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