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?
