The size of some computable object's minimal description is closely related to the object's probability. For instance, Levin [#!Levin:74!#] proved the remarkable Coding Theorem for his universal discrete enumerable semimeasure m based on halting programs (see Def. 4.11); compare independent work by Chaitin [#!Chaitin:75!#] who also gives credit to N. Pippenger:
In this special case, the contributions of the shortest programs dominate the probabilities of objects computable in the traditional sense. As shown by Gács [#!Gacs:83!#] for the case of MTMs, however, contrary to Levin's [#!Levin:73a!#] conjecture, but a slightly worse bound does hold:
The term -1 on the left-hand side stems from the definition of . We will now consider the case of probability distributions that dominate m, and semimeasures that dominate , starting with the case of enumerable objects.