Probability vs Descriptive Complexity

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

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI