The size of some computable object's minimal description is closely related to the object's probability. This is illustrated by Levin's Coding Theorem [29] for the universal discrete enumerable semimeasure based on halting programs (see Def. 4.11); compare independent work by Chaitin [14] 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 [17] for the case of MTMs, however, contrary to Levin's [28] conjecture, but a slightly worse bound does hold:
The term on the left-hand side stems from the definition of . We will now consider the case of probability distributions that dominate , and semimeasures that dominate , starting with the case of c.e. objects.