Thermodynamics of computation: A quest to find the cost of running a Turing machine

Turing machines were first proposed by British mathematician Alan Turing in 1936, and are a theoretical mathematical model of what it means for a system to “be a computer.”

At a high level, these machines are similar to real-world modern computers because they have storage for digital data and programs (somewhat like a hard drive), a little central processing unit (CPU) to perform computations, and can read programs from their storage, run them, and produce outputs. Amazingly, Turing proposed his model before real-world electronic computers existed.

In a paper published in the American Physical Society’s Physical Review Research, Santa Fe Institute researchers Artemy Kolchinsky and David Wolpert present their work exploring the thermodynamics of computation within the context of Turing machines.

“Our hunch was that the physics of Turing machines would show a lot of rich and novel structure because they have special properties that simpler models of computation lack, such as universality,” says Kolchinsky.

Turing machines are widely believed to be universal, in the sense that any computation done by any system can also be done by a Turing machine.

The quest to find the cost of running a Turing machine began with Wolpert trying to use information theory — the quantification, storage, and communication of information — to formalize how complex a given operation of a computer is. While not restricting his attention to Turing machines per se, it was clear that any results he derived would have to apply to them as well.

During the process, Wolpert stumbled onto the field of stochastic thermodynamics. “I realized, very grudgingly, that I had to throw out the work I had done trying to reformulate nonequilibrium statistical physics, and instead adopt stochastic thermodynamics,” he says. “Once I did that, I had the tools to address my original question by rephrasing it as: In terms of stochastic thermodynamics cost functions, what’s the cost of running a Turing machine? In other words, I reformulated my question as a thermodynamics of computation calculation.”

Thermodynamics of computation is a subfield of physics that explores what the fundamental laws of physics say about the relationship between energy and computation. It has important implications for the absolute minimum amount of energy required to perform computations.

Wolpert and Kolchinsky’s work shows that relationships exist between energy and computation that can be stated in terms of algorithmic information (which defines information as compression length), rather than “Shannon information” (which defines information as reduction of uncertainty about the state of the computer).

Put another way: The energy required by a computation depends on how much more compressible the output of the computation is than the input. “To stretch a Shakespeare analogy, imagine a Turing machine reads-in the entire works of Shakespeare, and then outputs a single sonnet,” explains Kolchinsky. “The output has a much shorter compression than the input. Any physical process that carries out that computation would, relatively speaking, require a lot of energy.”

While important earlier work also proposed relationships between algorithmic information and energy, Wolpert and Kolchinsky derived these relationships using the formal tools of modern statistical physics. This allows them to analyze a broader range of scenarios and to be more precise about the conditions under which their results hold than was possible by earlier researchers.

“Our results point to new kinds of relationships between energy and computation,” says Kolchinsky. “This broadens our understanding of the connection between contemporary physics and information, which is one of the most exciting research areas in physics.”

###