# Relation Between Different Definitions of Information Distance

I'm reading the fourth edition of An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi. In Section 8.3 of the book, it introduces the concept of "information distance." Intuitively, the "information distance" between two strings $$x$$ and $$y$$ is the minimum number of bits of information required to construct $$x$$ when given $$y$$ and vice versa. The book discusses various possible ways of formalizing this concept, and proves several theorems that demonstrate that these different definitions of information distance (with different motivations) are more-or-less equivalent.

All of the book's definitions of information distance rely on the idea of a universal prefix Turing machine. Prefix Turing machines are Turing machines where the set of halting programs is prefix free. A universal prefix Turing machine is a prefix Turing machine that can simulate any other prefix Turing machine given: (1) a self-delimiting encoding of the Turing machine's index in some effective enumeration of prefix Turing machines, (2) an input for the indexed prefix Turing machine, and (3) a self-delimiting "conditional" input to prepend to the input from (2). More precisely, if $$U$$ is the universal prefix Turing machine, $$i'$$ is a self-delimiting encoding of the index of prefix Turing machine $$T_i$$, $$y'$$ is the self-delimiting conditional input, and $$q$$ is the input, then $$U(y'i'q) = T_i(y'q)$$.

One way of defining the information distance between strings $$x$$ and $$y$$ is as the length of the shortest program for the universal prefix Turing machine that will output $$x$$ given $$y$$ as conditional input and vice versa (such a program is called a "conversion program" in the book). In other words, the information distance between $$x$$ and $$y$$ according to this definition is the length of the shortest program $$p$$ such that $$U(y'p) = x$$ and $$U(x'p) = y$$, where $$x'$$ and $$y'$$ are self-delimiting encodings of $$x$$ and $$y$$. Let $$E_0(x,y)$$ represent the information distance between strings $$x$$ and $$y$$ according to this definition.

Another way the book proposes measuring information distance involves universal reversible prefix Turing machines. Basically, reversible prefix Turing machines are prefix Turing machines where the mapping from input to output is one-to-one for all inputs for which the Turing machine halts. A universal reversible prefix Turing machine is similar to a universal prefix Turing machine, except the self-delimiting index input indexes over an effective enumeration of reversible prefix Turing machines rather than all prefix Turing machines. The book proposes that another possible definition of information distance between strings $$x$$ and $$y$$ is the length of the shortest program $$p$$ for which the universal reversible prefix Turing machine outputs $$y$$ given $$x$$ as conditional input. In other words, the information distance between $$x$$ and $$y$$ is the length of the shortest program $$p$$ such that $$UR(x'p) = y$$, where $$UR$$ is the universal reversible prefix Turing machine. Let $$E_2(x,y)$$ represent the information distance between strings $$x$$ and $$y$$ according to this definition.

Theorem 8.3.3 (p. 670) in the book states that $$E_2(x,y) = E_0(x,y)$$ up to an additive constant (i.e. there is a constant $$c$$ such that $$|E_2(x,y) - E_0(x,y)| <= c$$ for all strings $$x, y$$). One component of the proof involves proving that $$E_2(x,y) >= E_0(x,y)$$ (again up to an additive constant). The book points out that since reversible prefix Turing machines are a subset of prefix Turing machines, there is some index $$j$$ such that $$UR(x'p) = U(x'j'p)$$ for all $$x$$ and $$p$$. The book says that this proves that $$E_2(x,y) >= E_0(x,y)$$.

This is where I get lost. In particular, I don't think it's necessarily the case that for shortest program $$p$$ such that $$UR(x'p) = y$$ we also have that $$UR(y'p) = x$$, so $$j'p$$ isn't necessarily a conversion program for the universal prefix Turing machine that converts $$x$$ to $$y$$ and vice versa (i.e. while $$U(x'j'p) = y$$, it's not necessarily the case that $$U(y'j'p) = x$$). There is a proof of the same theorem in a separate paper (available here on p. 24) that states that "we can reverse a reversible program by adding an $$O(1)$$ bit prefix program to it saying 'reverse the following program'" (i.e. if you are given a reversible program $$p$$ that converts $$x$$ to $$y$$, that same program can be "inverted" with constant overhead to convert $$y$$ to $$x$$ since $$p$$'s input-output mapping is one-to-one). While this is true, I'm not getting how the result that $$E_2(x,y) >= E_0(x,y)$$ follows, since it seems like any conversion program that leverages the shortest reversible program to convert in both directions would need to be able to determine whether the conditional input is $$x$$ or $$y$$ (in order to determine whether to run the reversible program "forwards" or "backwards"). I think the length of any code to distinguish between two strings will in general depend on the length of those strings.

Any ideas about what I'm missing or alternative ways to prove that $$E_2(x,y) >= E_0(x,y)$$?

Thanks for any help in advance and apologies if I'm missing something very obvious!