Similarly, some 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 [14]. is c.e. (dovetail over
all programs and sum up the contributions of the halting ), but
there is no recursive upper bound on the number of
instructions required to compute , given . This implies
[14] and also
. It is easy to see, however,
that on nonhalting EOMs there are much more compact descriptions:

(9) |

Juergen Schmidhuber 2003-02-13