<p>Regarding &quot;&quot;&quot;I think the length of any code to distinguish between two strings will in general depend on the length of those strings.&quot;&quot;&quot;</p>
<p>Indeed, there is a lower bound that is logarithmic in min(|x|,|y|) to solve this task.</p>
<p>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 -&gt; y or y -&gt; x direction needs to be evaluated, thus
<span class="math-container">$$
E'_0(x,y) = \min \{|p| : U(p,0x) = y \text{ and } U(p,1y) = x\}
$$</span></p>
<p>As you point out, theorem 8.3.3 only proves that the revertible distance <span class="math-container">$E_2$</span> equals the bidirectional information distance up to additive +O(1).</p>
<p>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 <a href="https://arxiv.org/pdf/2009.00469.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/2009.00469.pdf</a> .)</p>
<p>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.</p>
<p>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 <a href="https://arxiv.org/pdf/2009.00469.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/2009.00469.pdf</a> .) Also note that Paul Vitanyi switched to plain complexity in one of hist last papers: <a href="https://homepages.cwi.nl/%7Epaulv/papers/exact.pdf" rel="nofollow noreferrer">https://homepages.cwi.nl/~paulv/papers/exact.pdf</a> 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.</p>
<p>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|.</p>
<p>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.</p>

CC BY-SA 4.0
2024-02-02T01:28:26.507Z
This is extremely helpful, thanks so much for your response!
Ravi Deedwania
CC BY-SA 4.0
2024-01-31T17:33:00.167Z
2024-02-02T14:29:48.350Z
2024-02-02T14:29:48.350Z
Bruno Bauwens
<p>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 &quot;information distance.&quot; Intuitively, the &quot;information distance&quot; between two strings <span class="math-container">$x$</span> and <span class="math-container">$y$</span> is the minimum number of bits of information required to construct <span class="math-container">$x$</span> when given <span class="math-container">$y$</span> 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.</p>
<p>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 &quot;conditional&quot; input to prepend to the input from (2). More precisely, if <span class="math-container">$U$</span> is the universal prefix Turing machine, <span class="math-container">$i'$</span> is a self-delimiting encoding of the index of prefix Turing machine <span class="math-container">$T_i$</span>, <span class="math-container">$y'$</span> is the self-delimiting conditional input, and <span class="math-container">$q$</span> is the input, then <span class="math-container">$U(y'i'q) = T_i(y'q)$</span>.</p>
<p>One way of defining the information distance between strings <span class="math-container">$x$</span> and <span class="math-container">$y$</span> is as the length of the shortest program for the universal prefix Turing machine that will output <span class="math-container">$x$</span> given <span class="math-container">$y$</span> as conditional input and vice versa (such a program is called a &quot;conversion program&quot; in the book). In other words, the information distance between <span class="math-container">$x$</span> and <span class="math-container">$y$</span> according to this definition is the length of the shortest program <span class="math-container">$p$</span> such that <span class="math-container">$U(y'p) = x$</span> and <span class="math-container">$U(x'p) = y$</span>, where <span class="math-container">$x'$</span> and <span class="math-container">$y'$</span> are self-delimiting encodings of <span class="math-container">$x$</span> and <span class="math-container">$y$</span>. Let <span class="math-container">$E_0(x,y)$</span> represent the information distance between strings <span class="math-container">$x$</span> and <span class="math-container">$y$</span> according to this definition.</p>
<p>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 <span class="math-container">$x$</span> and <span class="math-container">$y$</span> is the length of the shortest program <span class="math-container">$p$</span> for which the universal reversible prefix Turing machine outputs <span class="math-container">$y$</span> given <span class="math-container">$x$</span> as conditional input. In other words, the information distance between <span class="math-container">$x$</span> and <span class="math-container">$y$</span> is the length of the shortest program <span class="math-container">$p$</span> such that <span class="math-container">$UR(x'p) = y$</span>, where <span class="math-container">$UR$</span> is the universal reversible prefix Turing machine. Let <span class="math-container">$E_2(x,y)$</span> represent the information distance between strings <span class="math-container">$x$</span> and <span class="math-container">$y$</span> according to this definition.</p>
<p>Theorem 8.3.3 (p. 670) in the book states that <span class="math-container">$E_2(x,y) = E_0(x,y)$</span> up to an additive constant (i.e. there is a constant <span class="math-container">$c$</span> such that <span class="math-container">$|E_2(x,y) - E_0(x,y)| &lt;= c$</span> for all strings <span class="math-container">$x, y$</span>). One component of the proof involves proving that <span class="math-container">$E_2(x,y) &gt;= E_0(x,y)$</span> (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 <span class="math-container">$j$</span> such that <span class="math-container">$UR(x'p) = U(x'j'p)$</span> for all <span class="math-container">$x$</span> and <span class="math-container">$p$</span>. The book says that this proves that <span class="math-container">$E_2(x,y) &gt;= E_0(x,y)$</span>.</p>
<p>This is where I get lost. In particular, I don't think it's necessarily the case that for shortest program <span class="math-container">$p$</span> such that <span class="math-container">$UR(x'p) = y$</span> we also have that <span class="math-container">$UR(y'p) = x$</span>, so <span class="math-container">$j'p$</span> isn't necessarily a conversion program for the universal prefix Turing machine that converts <span class="math-container">$x$</span> to <span class="math-container">$y$</span> and vice versa (i.e. while <span class="math-container">$U(x'j'p) = y$</span>, it's not necessarily the case that <span class="math-container">$U(y'j'p) = x$</span>). There is a proof of the same theorem in a separate paper (available <a href="https://arxiv.org/pdf/1006.3520.pdf" rel="nofollow noreferrer">here</a> on p. 24) that states that &quot;we can reverse a reversible program by adding an <span class="math-container">$O(1)$</span> bit prefix program to it saying 'reverse the following program'&quot; (i.e. if you are given a reversible program <span class="math-container">$p$</span> that converts <span class="math-container">$x$</span> to <span class="math-container">$y$</span>, that same program can be &quot;inverted&quot; with constant overhead to convert <span class="math-container">$y$</span> to <span class="math-container">$x$</span> since <span class="math-container">$p$</span>'s input-output mapping is one-to-one). While this is true, I'm not getting how the result that <span class="math-container">$E_2(x,y) &gt;= E_0(x,y)$</span> 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 <span class="math-container">$x$</span> or <span class="math-container">$y$</span> (in order to determine whether to run the reversible program &quot;forwards&quot; or &quot;backwards&quot;). I think the length of any code to distinguish between two strings will in general depend on the length of those strings.</p>
<p>Any ideas about what I'm missing or alternative ways to prove that <span class="math-container">$E_2(x,y) &gt;= E_0(x,y)$</span>?</p>
<p>Thanks for any help in advance and apologies if I'm missing something very obvious!</p>

<it.information-theory><kolmogorov-complexity>
Relation Between Different Definitions of Information Distance
Ravi Deedwania
# Relation Between Different Definitions of Information Distance

(Asked by: username_0 on 2023-11-10)

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](https://arxiv.org/pdf/1006.3520.pdf) 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!

**Tags:** it.information-theory, kolmogorov-complexity

---

## 1 answers

### Answer by username_1 on 2024-01-31. Score: 0 | Accepted answer

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](https://homepages.cwi.nl/%7Epaulv/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.

> **Comments:**
> **username_0**: This is extremely helpful, thanks so much for your response!  

---

