Probability vs Descriptive Complexity next up previous contents
Next: Theorems for EOMs and Up: No Title Previous: Universal CEM vs EOM

   
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:

Theorem 5.1 (Coding Theorem)  

\begin{displaymath}For~x \in B^*,~
-log~m(x) \leq K(x) \leq -log~m(x) + O(1)
\end{displaymath} (36)

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

Theorem 5.2  

\begin{displaymath}K\mu^M(x) - 1 \leq Km^M(x) \leq K\mu^M(x) + Km^M(K\mu^M(x)) + O(1).
\end{displaymath} (37)

 

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 enumerable objects.



 
next up previous contents
Next: Theorems for EOMs and Up: No Title Previous: Universal CEM vs EOM
Juergen Schmidhuber
2001-01-09


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