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

Date:
August 26, 2020
Source:
Santa Fe Institute
Summary:
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.

In a new article, researchers present their work exploring the
energetic costs of computation within the context of Turing
machines.



FULL STORY ========================================================================== 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."

========================================================================== Story Source: Materials provided by Santa_Fe_Institute. Note: Content
may be edited for style and length.


========================================================================== Journal Reference:
1. Artemy Kolchinsky, David H. Wolpert. Thermodynamic costs of Turing
machines. Physical Review Research, 2020; 2 (3) DOI: 10.1103/
PhysRevResearch.2.033312 ==========================================================================

Link to news story: https://www.sciencedaily.com/releases/2020/08/200826175641.htm

--- up 2 days, 6 hours, 51 minutes
* Origin: -=> Castle Rock BBS <=- Now Husky HPT Powered! (1337:3/111)