Normalized Information Distance is Not Semicomputable

Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitanyi

Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of…