Nav: Home

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


Santa Fe Institute

Related Relationships Articles:

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.
More Relationships News and Relationships Current Events

Trending Science News

Current Coronavirus (COVID-19) News

Top Science Podcasts

We have hand picked the top science podcasts of 2020.
Now Playing: TED Radio Hour

Listen Again: The Power Of Spaces
How do spaces shape the human experience? In what ways do our rooms, homes, and buildings give us meaning and purpose? This hour, TED speakers explore the power of the spaces we make and inhabit. Guests include architect Michael Murphy, musician David Byrne, artist Es Devlin, and architect Siamak Hariri.
Now Playing: Science for the People

#576 Science Communication in Creative Places
When you think of science communication, you might think of TED talks or museum talks or video talks, or... people giving lectures. It's a lot of people talking. But there's more to sci comm than that. This week host Bethany Brookshire talks to three people who have looked at science communication in places you might not expect it. We'll speak with Mauna Dasari, a graduate student at Notre Dame, about making mammals into a March Madness match. We'll talk with Sarah Garner, director of the Pathologists Assistant Program at Tulane University School of Medicine, who takes pathology instruction out of...
Now Playing: Radiolab

What If?
There's plenty of speculation about what Donald Trump might do in the wake of the election. Would he dispute the results if he loses? Would he simply refuse to leave office, or even try to use the military to maintain control? Last summer, Rosa Brooks got together a team of experts and political operatives from both sides of the aisle to ask a slightly different question. Rather than arguing about whether he'd do those things, they dug into what exactly would happen if he did. Part war game part choose your own adventure, Rosa's Transition Integrity Project doesn't give us any predictions, and it isn't a referendum on Trump. Instead, it's a deeply illuminating stress test on our laws, our institutions, and on the commitment to democracy written into the constitution. This episode was reported by Bethel Habte, with help from Tracie Hunte, and produced by Bethel Habte. Jeremy Bloom provided original music. Support Radiolab by becoming a member today at Radiolab.org/donate.     You can read The Transition Integrity Project's report here.