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) |