Relation Between Different Definitions of Information Distance

Question

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!

Answer 1

Regarding """I think the length of any code to distinguish between two strings will in general depend on the length of those strings."""

Indeed, there is a lower bound that is logarithmic in min(|x|,|y|) to solve this task.

Regarding your quesition. Alexander Shen proposed a directional variant of the information distance, where an extra bit is given in the input to indicate whether x -> y or y -> x direction needs to be evaluated, thus $$ E'_0(x,y) = \min \{|p| : U(p,0x) = y \text{ and } U(p,1y) = x\} $$

As you point out, theorem 8.3.3 only proves that the revertible distance $E_2$ equals the bidirectional information distance up to additive +O(1).

Aleksander Shen also asked me whether this directional variant equals the undirectional variant of the information distance. I could neither prove nor disprove this. (See the 1st open question in section 8 in https://arxiv.org/pdf/2009.00469.pdf .)

However, by the main results of the same paper it follows that the bidirectional and undirectional distances are equal up to O(log log |xy|) and in fact equal up to O(1) in most typical cases, for example if the lengths or the complexities of x and y differ by some subexponential function.

On the other hand, if E_0 were defined with plain complexity, then the bidirectional variant equals E_0. For the plain variants, it holds that E_0(x,y) = max{C(x|y), C(y|x)} + O(1). Since the directional variant of E_0 lies between max{C(x|y), C(y|x)} and the undirectional variant, this means that the undirectional and directional variants are the same up to O(1). (This is explained in remark 2.1 on page 4 in +my paper https://arxiv.org/pdf/2009.00469.pdf .) Also note that Paul Vitanyi switched to plain complexity in one of hist last papers: https://homepages.cwi.nl/~paulv/papers/exact.pdf Since the plain and the prefix distances are equal up to an additive logarithmic term in the distance, such considerations imply that theorem 8.3.3 holds up to additive logarithmic terms.

The reason why the prefix variant is often preferable is that it satisfies the triangle inequality with +O(1) precision. The plain variant violates it with a different of log |xy|.

Conclusion: Theorem 8.3.3 only holds up to O(log log E_0(x,y)) precision in general. Whether it holds up to +O(1) precision as claimed, is a difficult open question. If you do not care about the precision of the triangle inequality, then it is recommended to use the variants with plain complexity.