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

August 26, 2020

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."

Santa Fe Institute

Related Relationships Articles from Brightsurf:

Gorilla relationships limited in large groups
Mountain gorillas that live in oversized groups may have to limit the number of strong social relationships they form, new research suggests.

Electronic surveillance in couple relationships
Impaired intimacy, satisfaction, and infidelity in a romantic relationship can fuel Interpersonal Electronic Surveillance (IES).

'Feeling obligated' can impact relationships during social distancing
In a time where many are practicing 'social distancing' from the outside world, people are relying on their immediate social circles more than usual.

We can make predictions about relationships - but is this necessary?
'Predictions as to the longevity of a relationship are definitely possible,' says Dr Christine Finn from the University of Jena.

Disruptions of salesperson-customer relationships. Is that always bad?
Implications from sales relationship disruptions are intricate and can be revitalizing.

Do open relationships really work?
Open relationships typically describe couples in which the partners have agreed on sexual activity with someone other than their primary romantic partner, while maintaining the couple bond.

The 7 types of sugar daddy relationships
University of Colorado Denver researcher looks inside 48 sugar daddy relationships to better understand the different types of dynamics, break down the typical stereotype(s) and better understand how these relationships work in the United States.

Positive relationships boost self-esteem, and vice versa
Does having close friends boost your self-esteem, or does having high self-esteem influence the quality of your friendships?

Strong family relationships may help with asthma outcomes for children
Positive family relationships might help youth to maintain good asthma management behaviors even in the face of difficult neighborhood conditions, according to a new Northwestern University study.

In romantic relationships, people do indeed have a 'type'
Researchers at the University of Toronto show that people do indeed have a 'type' when it comes to dating, and that despite best intentions to date outside that type -- for example, after a bad relationship -- some will gravitate to similar partners.

Read More: Relationships News and Relationships Current Events is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to