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 *K*^{E}(*x*) is actually
bounded by *K*^{E}(*s*), the complexity of the enumerable number
with minimal *K*_{T}(*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:

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

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