Thermodynamic costs of Turing Machines

Abstract

Turing Machines (TMs) are the canonical model of computation in computer science and physics. We combine techniques from algorithmic information theory and stochastic thermodynamics to analyze the thermodynamic costs of TMs. We consider two different ways of realizing a given TM with a physical process. 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 realization that is computable (i.e., consistent with the physical Church-Turing thesis). We consider three different thermodynamic costs: the heat generated when the TM is run on each input (which we refer to as the "heat function"), 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), and the expected heat on the input distribution that minimizes entropy production. For universal TMs, we show for both realizations that the thermodynamic complexity of any desired output is bounded by a constant (unlike the conventional Kolmogorov complexity), while the expected amount of generated heat is infinite. We also show that any computable realization faces a fundamental tradeoff between heat generation, the Kolmogorov complexity of its heat function, and the Kolmogorov complexity of its input-output map. We demonstrate this tradeoff by analyzing the thermodynamics of erasing a long string.

Physical Review Research, 2020

References in corpus (6)

• High-precision test of Landauer's principle in a feedback trap
• Ensemble and Trajectory Thermodynamics: A Brief Introduction
• Experimental study of mutual information in a Maxwell Demon
• The thermodynamics of prediction
• Finite-time erasing of information stored in fermionic bits
• Relations between Entropies Produced in Nondeterministic Thermodynamic Processes

Cited by in corpus (11)

• Is stochastic thermodynamics the key to understanding the energy costs of computation?
• Thermodynamics of computations with absolute irreversibility, unidirectional transitions, and stochastic computation times
• Landauer Principle and Thermodynamics of Computation
• Dependence of integrated, instantaneous, and fluctuating entropy production on the initial state in quantum and classical processes
• Multiclass classification utilising an estimated algorithmic probability prior
• Thermodynamic cost of Brownian computers in the stochastic thermodynamics of resetting
• Simulation of reversible molecular mechanical logic gates and circuits
• Generalized Zurek's bound on the cost of an individual classical or quantum computation
• Dynamics of one-dimensional spin models under the line-graph operator
• The Complexity Dynamics of Grokking
• Pipelined information flow in molecular mechanical circuits leads to increased error and irreversibility