Thermodynamic costs of Turing Machines

Abstract

Turing Machines (TMs) are the canonical model of computation in both computer science and physics. We derive fundamental bounds on the minimal thermodynamic costs that must be incurred when running a TM. We consider two different physical realizations of a TM. The first realization is designed to be thermodynamically reversible when fed with random input bits. The second realization is designed to generate less heat, up to an additive constant, than any other realization allowed by the laws of physics, assuming that the "physical Church-Turing thesis" holds. For each realization, we consider three different thermodynamic costs: (1) the heat generated when the TM is run on different inputs, which we refer to as the "heat function"; (2) the minimum heat generated when a TM is run with an input that results in some desired output, which we refer to as the "thermodynamic complexity" of the output (in analogy to the Kolmogorov complexity); (3) the expected heat generated when a TM is run on a distribution of inputs. We show that for both realizations of a computationally universal TM, the thermodynamic complexity of any desired output is bounded by a constant. This contrasts with conventional Kolmogorov complexity, which is an unbounded function. At the same time, we show that the expected value of the thermodynamic Kolmogorov complexity is infinite. Finally, we uncover a fundamental trade-off between the heat generated by a realization of a TM and the Kolmogorov complexity of the realization's heat function.