Probability vs Descriptive Complexity

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.