Similarly, some *x* are compactly describable on EOMs
but not on MTMs. To see this,
consider Chaitin's ,
the halting probability of an MTM
whose input bits are obtained by tossing an unbiased coin whenever it
requests a new bit [#!Chaitin:87!#].
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
,
given *n*. This implies
[#!Chaitin:87!#] and also
.
It is easy to see, however,
that on nonhalting EOMs there are much more compact descriptions:

(11) |

that is, there is no upper bound of

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