next up previous
Next: Between EOMs and GTMs? Up: Probability vs Descriptive Complexity Previous: Novel Theorems for EOMs

Tighter Bounds?

Is it possible to get rid of the small correction terms such as $K^E(KP^E(x)) leq O(log(-log P^E(x))$ in Theorem 5.3? Note that the construction in the proof shows that $K^E(x)$ is actually bounded by $K^E(s)$, the complexity of the c.e. number $0.s in I(x)$ with minimal $K_T(s)$. The facts $sum_x P^M(x) = 1$, $sum_x P^E(x) = 1$, $sum_x P^G(x) < 1$, as well as intuition and wishful thinking inspired by Shannon-Fano Theorem [38] and Coding Theorem 5.1 suggest there might indeed be tighter bounds:

Conjecture 5.1   For $x in B^{sharp}$ with $P^M(x) > 0$: $P^M(x) = O(2^{-K^M(x)})$.

Conjecture 5.2   For $x in B^{sharp}$ with $P^E(x) > 0$: $P^E(x) = O(2^{-K^E(x)})$.

Conjecture 5.3   For $x in B^{sharp}$ with $P^G(x) > 0$: $P^G(x) = O(2^{-K^G(x)})$.

Gács has shown though that analogue conjectures for semimeasures such as $mu^M$ on $B^*$ (as opposed to distributions on $B^{sharp}$) are false [17].

Juergen Schmidhuber 2003-02-13