A string p is called a program to compute y given x
if U(p,x)=y, where U denotes universal programming language.
Kolmogorov complexity K(y|x) of y relative to x
is defined as minimum length of
a program to compute y given x.
Let K(x) denote K(x|\text{empty string})
(Kolmogorov complexity of x) and
let I(x:y)=K(x)+K(y)-K(\pair{x,y})
(the amount of mutual information in x,y).
In the present paper we answer in negative the following
question posed in~\cite{id}:
Is it true that for any
strings x,y there are
independent minimum length programs p,q to translate between x,y,
that is, is it true that
for any x,y there are p,q such that U(p,x)=y, U(q,y)=x,
the length of p is K(y|x),
the length of q is K(x|y), and
I(p:q)=0 (where the last three equalities hold up
to an additive O(\log(K(x|y)+K(y|x))) term)?