Is "normalized distance" (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing?
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.