Thermodynamics of computation and information distance

CH Bennett, P Gács, M Li, PMB Vitányi… - Proceedings of the twenty …, 1993 - dl.acm.org
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, 1993dl.acm.org
Intuitively, the minimal information distance between z and g is the length of the shortest
program for a universal computer to transform z into v and y into z. This measure will be
shown to be, up to a logarithmic additive term, equal to the maximum of the conditional
Kolmogorov complexities El (z, y)= max {~(ylz), K (zly)}. Any reasonable distance to measure
similarity of pictures should be an effectively approximable, symmetric, positive function of z
and y satisfying a reasonable normalization condition and obeying the triangle inequality. It …
Abstract
Intuitively, the minimal information distance between z and g is the length of the shortest program for a universal computer to transform z into v and y into z. This measure will be shown to be, up to a logarithmic additive term, equal to the maximum of the conditional Kolmogorov complexities El (z, y)= max {~(ylz), K (zly)}. Any reasonable distance to measure similarity of pictures should be an effectively approximable, symmetric, positive function of z and y satisfying a reasonable normalization condition and obeying the triangle inequality. It turns out that El is minimal up to an additive constant among all such dist antes. Hence it is a universal ‘picture dist ante’, which accounts for any effective similarity between pictures. A third information distance, based on the idea that one should aim for dissipationless computations, and hence for reversible ones, is given by the length Ez (z, y)= IOl (ylz)= Kl?(zly) of the shortest reversible program that transforms z into y and y into x on a universal reversible computer. It is shown that also EZ= El, up to a logarithmic additive term. It is remarkable that three so differently motivated definitions turn out to define one and the same notion. Another information distance, E3, is obtained by minimizing the total amount of information flowing in and out during a reversible computation in which the program is not retained, in other words the number of extra bits (apart from z) that must be irreversibly supplied at the beginning, plus the number of garbage bits (apart from y) that must be irreversibly erased at the end of the computation to obtain a ‘clean’ y. This distance is within a logarithmic additive term of the sum of the conditional complexities,.? 73 (z, y)= K (y [z)+ K (o\y).
Finally, using the physical theory of reversible computation, the simple difference K (z)–K (y) is shown to be an appropriate(universal, antisymmetric, and transitive) measure of the amount of thermodynamic work required to transform string a into string y by the most efficient process,
ACM Digital Library