INFORMATION DISTANCE

While Kolmogorov complexity is the accepted absolute measure of inform ation content in an individual finite object, a similarly absolute not ion is needed for the information distance between two individual obje cts, for example, two pictures. We give several natural definitions of a universal information metric, based on length of shortest programs for either ordinary computations or reversible (dissipationless) compu tations. It turns out that these definitions are equivalent up to an a dditive logarithmic term. We show that the information distance is a u niversal cognitive similarity distance. We investigate the maximal cor relation of the shortest programs involved, the maximal uncorrelation of programs (a generalization of the Slepian-Wolf theorem of classical information theory), and the density properties of the discrete metri c spaces induced by the information distances, A related distance meas ures the amount of nonreversibility of a computation. Using the physic al theory of reversible computation, we give an appropriate (universal , antisymmetric, and transitive) measure of the thermodynamic work req uired to transform one object in another object by the most efficient process. Information distance between individual objects is needed in pattern recognition where one wants to express effective notions of '' pattern similarity'' or ''cognitive similarity'' between individual ob jects and in thermodynamics of computation where one wants to analyze the energy dissipation of a computation from a particular input to a p articular output.