Thermodynamic costs of Turing machines

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 trade-off among heat generation, the Kolmogorov complexity of its heat function, and the Kolmogorov complexity of its input-output map. We demonstrate this trade-off by analyzing the thermodynamics of erasing a long string.

Figure 1

A TM performing a computation. The update function is applied over a sequence of steps, causing the finite-state head (rounded box, states are colored circles) to move along an infinite tape of symbols ($\mathtt{b}$ indicates a special “blank” symbol). During each step, the head can read or write the tape symbol in the current position, move left or right along the tape, and change its current state (green triangle). The computation completes if and when the head reaches its halt state (red circle).

Figure 2

A realization of a TM is a physical process over a countable state space $\mathcal{X}\subseteq {\{0,1\}}^{*}$, which maps initial states to final states according to the input-output function of the TM. As a hypothetical example, consider a process that evolves to the final state $\mathtt{0110011}$ at $t=t_f$ when started on initial state $\mathtt{10101100}$ at $t=0$, as might correspond to a computation performed by the TM (see also Fig. 1).

Figure 3

Any computable process that realizes a deterministic input-output map $f$ faces a fundamental cost of $K\left(x\right|y)$ for mapping input $x$ to output $y=f\left(x\right)$. This cost can be paid through some combination of three different strategies: generating a large amount of heat, having a high complexity heat function, or having a high complexity input-output map $f$. This trade-off is illustrated on three axes, with blue indicating the feasible region.