1
$\begingroup$

Exercise 14.1 of Elements of Information Theory asks us to prove that there is a constant c such that

$$K(x,y)\leq K(x) +K(y)+c$$

for all binary strings $x,y$. Intuitively this seems true. Just write a program that first runs the program that $p_x$ that outputs $x$. Then the program $p_y$ that outputs $y$. Finally, output the tuple $(x,y)$. This program has length $K(x)+K(y)+c$. But it seems to me that there must be something wrong with this argument (and therefore also the exercise). Consider the computable function that concatenates two strings $f(x,y)=xy$. Then $$K(xy)=K(f(x,y))\leq K(x,y)+c \leq K(x)+K(y)+c'.$$ But this contradicts the fact that for any constant $c$, there exist strings $x$ and $y$ such that $$K(xy)>K(x)+K(y)+c.$$ This last fact is often stated (for example as an exercise in Sipser chapter 6).

I cannot formally prove the statement in Elements of Information Theory. Here is my attempt:

Let $D$ be the decompressor used in the definition of Kolmogorov complexity. Define $D'$ as $$D'(z)=(D(p_x),D(p_y))=(x,y)$$ when $z$ encodes a 2-tuple, and never halting otherwise. We encode a tuple by repeating each bit in each element of the tuple and using 01 as a seperator. Then $$K_{D'}(x,y)\leq 2K(x)+2K(y)+c,$$ which implies that $K(x,y)\leq 2K(x)+2K(y)+c'$.

My question: Is the exercise in Elements of Information Theory wrong, or am I misunderstanding something?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, it looks like the two claim are contradictory. I'm pretty sure the Sipser exercise is correct, though it's not trivial to verify. There is a useful hint here, but even given the hint it took me a couple hours. I won't spoil it here because it was honestly elucidating to work the problem out.

Your consideration of the details of encoding tuples is treated more explicitly in Sisper, and I agree it's good intuition for why the desired bound won't work: you always need super-constant bits to encode the pair of TMs.

I cannot find an errata to Elements of Information Theory so it seems the error is not well-known. I'm surprised they made this error, as other parts of the text talk about the overhead of encoding tuples. The error is also duplicated on the Wikipedia page for Kolmogorov complexity. It may be worth reaching out to the authors (but see if you can solve the Sipser exercise first!).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.