Thermodynamics of Turing Machines

Turing Machines [TMs] are the canonical model of computation. Using results from thermodynamics of computation, we investigate bounds on the amount of work required to perform calculations using TMs. First, we consider the minimal amount of work required to run a given input program on a TM. We also consider the minimal amount of work required to produce a given string as an output of a TM, in analogy to Kolmogorov complexity (which asks about the length of the shortest program needed to produce a given string on a TM). We analyze two ways of implementing a TM, one of which is shown to require less work than any computable implementation. We also show that unlike the Kolmogorov complexity of a string which can be arbitrarily large, the minimal amount of work required to produce a given string is bounded by a constant.