TR00-035 Authors: Nikolay Vereshchagin, Mikhail V. Vyugin

Publication: 6th June 2000 18:21

Downloads: 1363

Keywords:

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)?