Tighter Bounds?
Next: Between EOMs and GTMs? Up: Probability vs Descriptive Complexity Previous: Theorems for EOMs and

## Tighter Bounds?

Is it possible to get rid of the small correction terms such as in Theorem 5.3? Note that the construction in the proof shows that KE(x) is actually bounded by KE(s), the complexity of the enumerable number with minimal KT(s). The facts , , , as well as intuition and wishful thinking inspired by Shannon-Fano Theorem [#!Shannon:48!#] and Coding Theorem 5.1 suggest there might indeed be tighter bounds:

Conjecture 5.1   For with PM(x) > 0: .

Conjecture 5.2   For with PE(x) > 0: .

Conjecture 5.3   For with PG(x) > 0: .

The work of Gács has already shown, however, that analogue conjectures for semimeasures such as (as opposed to distributions) are false [#!Gacs:83!#].

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