Next: GTMs dominate EOMs Up: Expressiveness of EOMs and Previous: Expressiveness of EOMs and

### EOMs dominate MTMs

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)

that is, there is no upper bound of
 (10)

Juergen Schmidhuber 2003-02-13