  While Kolmogorov complexity is the accepted absolute measure of information
content in an individual finite object, a similarly absolute notion is needed
for the information distance between two individual objects, 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) computations. It turns out that these
definitions are equivalent up to an additive logarithmic term. We show that the
information distance is a universal cognitive similarity distance. We
investigate the maximal correlation 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
metric spaces induced by the information distances. A related distance measures
the amount of nonreversibility of a computation. Using the physical theory of
reversible computation, we give an appropriate (universal, anti-symmetric, and
transitive) measure of the thermodynamic work required 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 objects and in thermodynamics of computation where one wants to
analyse the energy dissipation of a computation from a particular input to a
particular output.
