<p>The distance should be upper semicomputable. For instance the Hamming distance or Euclidean distance as such is not. One has to turn them into a version that satisfies the requirement above. Read the paper closer. </p>

CC BY-SA 3.0
2014-11-24T22:51:45.170Z
I don't understand. Euclidean (or Hamming) distance is a computable function, and so certainly it is semi-computable, no?  Moreover, you did not answer my question: can you always turn a computable metric into a version that satisfies the definition above?
Jeremy Kun
CC BY-SA 3.0
2014-11-24T16:20:48.473Z
2014-11-24T16:20:48.473Z
guest
<p>In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the density requirement for every $x \in \Omega$ and every constant $c \in [0,1]$:</p>

<p>$\displaystyle |\left \{ y : d(x,y) \leq c \right \}| &lt; 2^{cK(x)+1}$</p>

<p>They give a somewhat convoluted example of a normalized version of the Hamming distance which satisfies this definition, and they prove that their normalized information distance satisfies this definition as well.</p>

<p>It is not at all clear to me that this definition represents a wide variety of "distance" measurements. Their conclusion is that because the normalized information distance is universal in this class of metrics, it is philosophically universal in all metrics we care about. But it's not even obvious to me that Euclidean distance (restricted to $\left \{0,1\right \}^n$) can be modified to satisfy this definition. That's not even close to mentioning distance measures for, say, language sentiment or other distances used in applications.</p>

<p>It would be great if we could say, for instance, that every computable metric has a normalized version which satisfies this definition. Is this known? If not, what is known?  </p>

CC BY-SA 3.0
2012-11-13T05:29:06.573Z
Perhaps this is not the appropriate place to ask this question?
Jeremy Kun
<it.information-theory><kolmogorov-complexity><metrics>
Is "normalized distance" (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing?
Jeremy Kun
# Is "normalized distance" (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing?

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

In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the density requirement for every $x \in \Omega$ and every constant $c \in [0,1]$:

$\displaystyle |\left \{ y : d(x,y) \leq c \right \}| < 2^{cK(x)+1}$

They give a somewhat convoluted example of a normalized version of the Hamming distance which satisfies this definition, and they prove that their normalized information distance satisfies this definition as well.

It is not at all clear to me that this definition represents a wide variety of "distance" measurements. Their conclusion is that because the normalized information distance is universal in this class of metrics, it is philosophically universal in all metrics we care about. But it's not even obvious to me that Euclidean distance (restricted to $\left \{0,1\right \}^n$) can be modified to satisfy this definition. That's not even close to mentioning distance measures for, say, language sentiment or other distances used in applications.

It would be great if we could say, for instance, that every computable metric has a normalized version which satisfies this definition. Is this known? If not, what is known?

**Tags:** it.information-theory, kolmogorov-complexity, metrics
> **Comments:**
> **username_0**: Perhaps this is not the appropriate place to ask this question?  

---

## 1 answers

### Answer by username_1 on 2014-11-24. Score: -3

The distance should be upper semicomputable. For instance the Hamming distance or Euclidean distance as such is not. One has to turn them into a version that satisfies the requirement above. Read the paper closer.

> **Comments:**
> **username_0**: I don't understand. Euclidean (or Hamming) distance is a computable function, and so certainly it is semi-computable, no?  Moreover, you did not answer my question: can you always turn a computable metric into a version that satisfies the definition above?  

---

