2
$\begingroup$

I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question.

The authors define the reference universal lower semicomputable semimeasure as

$$ \textbf{M}(x) = \sum 2^{-K(\mu)} \mu(x) $$

where the sum goes over all lower semicomputable semimeasures. Moreover, they name $\lambda_U(x)$ the probability that the reference universal monotone machine $U$ computes a string that begins with $x$ when provided with coin-flip input.

Question 1: the authors claim that the two quantities above are equal, probably intending equality up to a multiplicative constant. It seems to me, however, that the multiplicative term is not constant but is only bounded. This seems to be confirmed by the fact that they state what should be a Coding theorem as $$ -\log(\lambda_U(x)) = -\log(\textbf{M}(x)) + O(1)$$

Unfortunately they only sketch a proof, so it's not clear (to me at least) whether that $O(1)$ is actually a constant or not.
I would like to know whether equality (up to a multiplicative constant) actually holds, and in case, a reference to a proof would be appreciated.

Question 2: The authors claim $\textbf{M}$ is the probability that the reference universal monotone machine $U$ computes a string that begins with $x$ when provided with coin-flip input, but this interpretation is only allowed if equality (up to constant) holds among the two above quantities, otherwise I feel it is not legitimate. Am I wrong?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.