patternModerate
Is there a connection between the halting problem and thermodynamic entropy?
Viewed 0 times
problemthethermodynamichaltingbetweenentropyandthereconnection
Problem
Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem.
A TM is an abstract concept of a machine (or engine if you like). The Halting Theorem is an impossibility result. A Carnot Engine (CE) is an abstract concept of a heat engine and Carnot proved the Carnot Theorem, another impossibility result related to thermodynamic entropy.
Given that a TM is physically realizable (at least as much as a CE, or maybe not?) is there a mapping or representation or "isomorphism" of TM or CE which could allow to unify these results and in addition connect to entropy?
There are of course formulations of TM and the Halting Theorem in terms of algorithmic information theory (e.g. Chaitin, Kolmogorov etc.) and entropy (in that context). The question asks for the more physical concept of entropy (if in the process of a potential answer algorithmic entropy arises it is fine, but it is not what the question asks exactly).
One can also check another question in physics.se which relates quantum uncertainty with the 2nd law of thermodynamics. See also: an algebraic characterization of entropy, an algorithmic characterization of entropy, a review and connections between various formulations of entropy
A TM is an abstract concept of a machine (or engine if you like). The Halting Theorem is an impossibility result. A Carnot Engine (CE) is an abstract concept of a heat engine and Carnot proved the Carnot Theorem, another impossibility result related to thermodynamic entropy.
Given that a TM is physically realizable (at least as much as a CE, or maybe not?) is there a mapping or representation or "isomorphism" of TM or CE which could allow to unify these results and in addition connect to entropy?
There are of course formulations of TM and the Halting Theorem in terms of algorithmic information theory (e.g. Chaitin, Kolmogorov etc.) and entropy (in that context). The question asks for the more physical concept of entropy (if in the process of a potential answer algorithmic entropy arises it is fine, but it is not what the question asks exactly).
One can also check another question in physics.se which relates quantum uncertainty with the 2nd law of thermodynamics. See also: an algebraic characterization of entropy, an algorithmic characterization of entropy, a review and connections between various formulations of entropy
Solution
I am not at all an expert in this area, but I believe you will be interested in reversible computing. This involves, among other things, the study of the relationship between processes that are physically reversible and processes that are logically reversible. I think it would be fair to say that the "founders" of the field were/are Ralph Landauer and Charles H Bennett (both of IBM research, I think.)
It touches on quantum computing and quantum information theory, but also examines questions like "what are the limits of computation in terms of time, space and energy?" It is known, (if I remember correctly) that you can make the energy required to perform a reversible calculation arbitrarily small by making it take an arbitrarily long time. That is, energy $\times$ time (=action) required to perform a reversible computation can be made a constant. This is not the case for non-reversible computations.
Many of the people studying in this area are also working on quantum computing and digitial physics (the idea that the universe is a big quantum cellular automata). The researchers names that come to mind are Ed Fredkin, Tommaso Toffoli and Norm Margolus.
These questions are absolutely on topic for computer science. Not just for the theory (which includes cool math as well as cool physics) but for engineers who want to know the ultimate limits of computation. Is there a minimum volume or energy required to store a bit of information? The action required to perform a reversible computation may be constant, but are there limits on what that constant is? These are critical knowledge for engineers trying to push the boundaries of what is possible.
It touches on quantum computing and quantum information theory, but also examines questions like "what are the limits of computation in terms of time, space and energy?" It is known, (if I remember correctly) that you can make the energy required to perform a reversible calculation arbitrarily small by making it take an arbitrarily long time. That is, energy $\times$ time (=action) required to perform a reversible computation can be made a constant. This is not the case for non-reversible computations.
Many of the people studying in this area are also working on quantum computing and digitial physics (the idea that the universe is a big quantum cellular automata). The researchers names that come to mind are Ed Fredkin, Tommaso Toffoli and Norm Margolus.
These questions are absolutely on topic for computer science. Not just for the theory (which includes cool math as well as cool physics) but for engineers who want to know the ultimate limits of computation. Is there a minimum volume or energy required to store a bit of information? The action required to perform a reversible computation may be constant, but are there limits on what that constant is? These are critical knowledge for engineers trying to push the boundaries of what is possible.
Context
StackExchange Computer Science Q#26049, answer score: 13
Revisions (0)
No revisions yet.