Extending Landauer's Bound from Bit Erasure to Arbitrary Computation

Abstract

Recent analyses have calculated the minimal thermodynamic work required to perform a computation pi when two conditions hold: the output of pi is independent of its input (e.g., as in bit erasure); we use a physical computer C to implement pi that is specially tailored to the environment of C, i.e., to the precise distribution over C's inputs, P_0. First I extend these analyses to calculate the work required even if the output of pi depends on its input, and even if C is not used with the distribution P_0 it was tailored for. Next I show that if C will be re-used, then the minimal work to run it depends only on the logical computation pi, independent of the physical details of C. This establishes a formal identity between the thermodynamics of (re-usable) computers and theoretical computer science. I use this identity to prove that the minimal work required to compute a bit string sigma on a "general purpose computer" rather than a special purpose one, i.e., on a universal Turing machine U, is k_BT ln(2) times the sum of three terms: The Kolmogorov complexity of sigma, log of the Bernoulli measure of the set of strings that compute sigma, and log of the halting probability of U. I also prove that using C with a distribution over environments results in an unavoidable increase in the work required to run the computer, even if it is tailored to the distribution over environments. I end by using these results to relate the free energy flux incident on an organism / robot / biosphere to the maximal amount of computation that the organism / robot / biosphere can do per unit time.

10 pages, 1 figure

Cited by in corpus (10)

• Semantic information, autonomous agency, and nonequilibrium statistical physics
• Stochastic thermodynamics of computation
• The thermodynamic efficiency of computations made in cells across the range of life
• Exploring the landscapes of "computing": digital, neuromorphic, unconventional -- and beyond
• Uncertainty relations and fluctuation theorems for Bayes nets
• Number of hidden states needed to physically implement a given conditional distribution
• The free energy requirements of biological organisms; implications for evolution
• Dependence of integrated, instantaneous, and fluctuating entropy production on the initial state in quantum and classical processes
• A thermodynamically consistent model of finite state machines
• Overview of Information Theory, Computer Science Theory, and Stochastic Thermodynamics for Thermodynamics of Computation