Thermodynamics of computation and information distance
Charles H. Bennett, Péter Gács, Ming Li, Paul M. B. Vitanyi, Wojciech Hubert Zurek · 1993
Applying the tools of algorithmic information theory, we compare several candidates for an asymptotically machine-independent. absolute measure of the informational or ``cognitive`` distance between discrete objects x and y. The maximum of the conditional Kolmogorov complexities max{l_brace}K(y{vert_bar}z) K(m{vert_bar}y){r_brace}, is shown to be optimal, in the sense of being minimal within an additive constant among semicomputable, symmetric, positive semidefinite functions of z and y satisfying a reasonable normalization condition and obeying the triangle intequality. The optimal metric, in turn, differs by at most an additive logarithmic term from the size of the smallest program for a universal reversible computer to transform x into y. This program functions in a `catalytic`` capacity, being retained in the computer before, during, and after the computation. Similarly, the sum of the conditional complexities. K(y{vert_bar}x) + K(x{vert_bar}y), is shown to be equal within a logarithmic term to the minimal amount Of information flowing out and in during a reversible computation in which the program is not retained. Finally. using the physical theory of reversible computation, it is shown that the simple difference K(x) - K(y) is an appropriate (ie universal, antisymmetric, and transitive) measure of the amount of thermodynamic work required to transform string x into string y by the most efficient process.