Extending Landauer's Bound from Bit Erasure to Arbitrary Computation

Recent analyses have calculated the minimal thermodynamic work required to perform any computation $\pi$ whose output is independent of its input, e.g., bit erasure. First I extend these analyses to calculate the work required even if the output of $\pi$ depends on its input. Next I show that if a physical computer $\mathcal{C}$ implementing a computation $\pi$ will be re-used, then the work required depends only on the dynamics of the logical variables under $\pi$, independent of the physical details of $\mathcal{C}$. This establishes a formal identity between the thermodynamics of (re-usable) computers and theoretical computer science. To illustrate this identity, I prove that the minimal work required to compute a bit string $\sigma$ on a (physical) Turing machine $M$ is $k_BT\ln(2) \big[$Kolmogorov complexity($\sigma) \;+$ log (Bernoulli measure of the set of strings that compute $\sigma) \;+ $ log(halting probability of $M)\big]$. I also prove that uncertainty about the distribution over inputs to the computer increases the minimal work required to run the computer. 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.