  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.
