# Kolmogorov complexity of tuples

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?