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 $m$ based on halting programs (see Def. 4.11); compare independent work by Chaitin [14] who also gives credit to N. Pippenger:

Theorem 5.1 (Coding Theorem)  

$$For x \in B^*,  -log m(x) \leq K(x) \leq -log m(x) + O(1)$$ (34)

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, $mu^M(x) neq O(2^{-Km^M(x)});$ but a slightly worse bound does hold:

Theorem 5.2  

$$K\mu^M(x) - 1 \leq Km^M(x) \leq K\mu^M(x) + Km^M(K\mu^M(x)) + O(1).$$ (35)

The term $-1$ on the left-hand side stems from the definition of $lg(x) leq log(x)$. We will now consider the case of probability distributions that dominate $m$, and semimeasures that dominate $mu^M$, starting with the case of c.e. objects.