Theory Of Thermodynamics Of Computation
Ming Li, Paul M. B. Vitanyi · 2005
We investigate a new research area: we are interested in the ultimate thermodynamic cost of computing from x to y. Other than its fundamental importance, such research has implications for future miniaturization of VLSI chips reducing the energy dissipation below kT (thermal noise), and the similarity distance problem in pattern recognition. It turns out that the theory of thermodynamic cost of computation can be axiomatically developed. Our fundamental theorem connects physics to mathematics, providing the key that makes such a theory possible. It establishes optimal upper and lower bounds on the ultimate thermodynamic cost of computation. By computing longer and longer, the amount of dissipated energy gets closer to these limits. In fact, one can trade time for energy: there is a provable timeenergy trade-off hierarchy. The fundamental theorem also induces a thermodynamic distance metric. The topological properties of this metric show that neighborhoods are sparse, and get even spar...