But if the additive constant gap is true then I don’t think it’s a big deal technically (though it may still be significant pedagogically, and it’s weird that it’s not easy to find a reference for this claim if it’s needed for k-complexity to be a reasonable definition)
There is an easy-to-find reference of this claim: The coding theorem, Theorem 4.3.3 in Li and Vitányi’s “An Introduction to Kolmogorov Complexity and Its Applications”, which was introduced to me as the most well-known book on algorithmic information theory.
There is an easy-to-find reference of this claim: The coding theorem, Theorem 4.3.3 in Li and Vitányi’s “An Introduction to Kolmogorov Complexity and Its Applications”, which was introduced to me as the most well-known book on algorithmic information theory.