Properties of Algorithmic Information Distance
Marcus Hütter · IEEE Transactions on Information Theory · 2025
The domain-independent universal Normalized Information Distance based on Kolmogorov complexity has been (in approximate form) successfully applied to a variety of difficult clustering problems. In this paper we investigate theoretical properties of the un-normalized algorithmic information distance$d_{K}$. The main question we are asking in this work is what properties this curious distance has, besides being a metric. We show that many (in)finite-dimensional spaces can(not) be isometrically scale-embedded into the space of finite strings with metric$d_{K}$. We also show that$d_{K}$is not an Euclidean distance, but any finite set of points in Euclidean space can be scale-embedded into$(\{0,1\}^{*},d_{K})$. A major contribution is the development of the necessary framework and tools for finding more (interesting) properties of$d_{K}$in future, and to state several open problems.