<p>Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there is an important difference between <em>energy</em> needed to make a computation run, and <em>entropy</em> generated by the computation and put out into the environment, typically in the form of heat.)</p>
<p>Based on Landauer and Bennett's original analysis that erasing a bit &quot;must&quot; generate <span class="math-container">$kT \ln(2)$</span> entropy (see below for why there are scare-quotes), several researchers have pursued various questions along these lines. One line of research was to simulate irreversible Turing machines by reversible ones, which, it was suggested, would generate no entropy. There are several works showing space-time tradeoffs for how to simulate irreversible TMs by reversible ones, e.g.:</p>
<blockquote>
<ul>
<li><p>Bennett, <a href="https://doi.org/10.1137/0218053" rel="noreferrer">Time/Space Trade-Offs for Reversible Computation</a>. SICOMP 1989</p>
</li>
<li><p>Levine &amp; Sherman. <a href="https://doi.org/10.1137/0219046" rel="noreferrer">A Note on Bennett’s Time-Space Tradeoff for Reversible Computation</a>. SICOMP 1990.</p>
</li>
<li><p>Li &amp; Vitanyi. <a href="https://doi.org/10.1109/CCC.1996.507692" rel="noreferrer">Reversible simulation of irreversible computation</a>. CCC 1996</p>
</li>
<li><p>Lange, McKenzie, and Tapp. <a href="https://doi.org/10.1006/jcss.1999.1672" rel="noreferrer">Reversible Space Equals Deterministic Space</a>. JCSS 2000.</p>
</li>
</ul>
</blockquote>
<p>More recently,</p>
<blockquote>
<p>Demaine, Lynch, Mirano, and Tyagi. <a href="https://arxiv.org/abs/1605.08448" rel="noreferrer">Energy-Efficient Algorithms</a>, 2016.</p>
</blockquote>
<p>studied partially reversible algorithms - that is, if you are willing to pay some entropy, for standard algorithmic tasks can one improve upon the general irreversible-to-reversible simulations mentioned above. Reversible computing has a whole community of researchers devoted to it, viz. the <a href="http://www.reversible-computation.org/" rel="noreferrer">Reversible Computing</a> conference, now in its 10th year.</p>
<p>It has actually been known for a long time, going all the way back to Landauer and Bennett, that the relationship between computational irreversibility and entropy generation is more subtle than is suggested by the tagline &quot;erasing a bit generates <span class="math-container">$\ln(2)$</span> entropy.&quot; However, in the past 20 years or so nonequilibrium statistical mechanics has advanced to the point that this more subtle relationship can be captured by precise numerical equations involving not just entropy difference, but also a difference of KL divergences, see</p>
<blockquote>
<p>Kolchinsky &amp; Wolpert, <a href="https://dx.doi.org/10.1088/1742-5468/aa7ee1" rel="noreferrer">Dependence of dissipation on the initial distribution over states</a>. J. Stat. Mech. 2017 (<a href="https://arxiv.org/abs/1607.00956" rel="noreferrer">arXiv link</a>)</p>
</blockquote>
<p>(and references therein).</p>
<p>We hosted a <a href="https://www.santafe.edu/events/thermodynamics-and-computation-towards-new-synthes" rel="noreferrer">workshop on this at the Santa Fe Institute</a> in August 2017 (where you can see the names of some researchers and talk titles of relevance), and it raises a whole new set of questions in both physics and thermodynamic computational complexity.</p>

CC BY-SA 3.0
2018-02-03T02:56:54.510Z
Turing Machine or Church-Turing Thesis may be ruled or restricted by physical law, so the possibility whether quantum computation or quantum communication can be implemented may be deduced from physics law, like the second law of  statistical mechanics, general relativity. So I guess if there is any result about the linkage of the thesis and physics law
XL _At_Here_There
CC BY-SA 3.0
2018-02-03T03:48:28.613Z
And it seems that physics site is not interested in the topics of this kind.
XL _At_Here_There
CC BY-SA 3.0
2018-02-03T06:39:42.850Z
@XL_at_China: There is a "Physical Church-Turing thesis", but this has little to do with the second law, since both the Church-Turing thesis and its physical version are just about what is computable, not about any kind of quantitative estimates, but the second law is a quantitative statement. Also, while there may not have yet been a ton of publications on it, at our workshop the physicists definitely seemed interested.
Joshua Grochow
CC BY-SA 3.0
2018-02-03T09:06:23.373Z
I had tried to find the linkage several years ago,  but failed to get any result. Intuitively, the computability seems  to have to be  linked to the second thermodynamic law. And considering Turing Machine in the term of general relativity, the problem becomes interesting. But I do not know any physicists are interested in such a problem.
XL _At_Here_There
CC BY-SA 3.0
2018-02-03T13:17:50.827Z
And could we post a related question on physics of the site, and discuss it with physicist?
XL _At_Here_There
CC BY-SA 4.0
2020-08-02T13:03:56.307Z
Having not read the papers you posted as reference， I have known the topics of the field eventually
XL _At_Here_There
CC BY-SA 3.0
2018-02-02T10:15:37.697Z
2018-02-02T10:15:37.697Z
2020-06-17T09:38:08.363Z
Joshua Grochow
<p>There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, computational complexity $F(n) $ is correlated to the average consumption of energy, hope I can get some answer here.</p>

CC BY-SA 3.0
2018-02-04T08:25:45.857Z
Linking to the paper in question would improve this question.
Stella Biderman
CC BY-SA 3.0
2018-02-04T08:37:16.743Z
@StellaBiderman thank you, but I have found no link in your comment.
XL _At_Here_There
CC BY-SA 3.0
2018-02-04T14:39:22.433Z
I don’t know what paper/researcher you’re talking about. I’m suggesting that you provide I
Stella Biderman
CC BY-SA 3.0
2018-02-05T03:29:27.037Z
@StellaBiderman I misunderstood your comments, actually I just read a text realating "erasing bit has to consume energy" in Kolmogorov complexity and its application by  Viatanyi and Li. I think I have not read any other relating articles and books
XL _At_Here_There
<cc.complexity-theory><reference-request><it.information-theory><quantum-information><statistical-physics>
Entropy and computational complexity
XL _At_Here_There
# Entropy and computational complexity

(Asked by: username_0 on 2018-02-02)

There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, computational complexity $F(n) $ is correlated to the average consumption of energy, hope I can get some answer here.

**Tags:** cc.complexity-theory, reference-request, it.information-theory, quantum-information, statistical-physics

> **Comments:**
> **username_1**: Linking to the paper in question would improve this question.  
> **username_0**: @StellaBiderman thank you, but I have found no link in your comment.  
> **username_1**: I don’t know what paper/researcher you’re talking about. I’m suggesting that you provide I  
> **username_0**: @StellaBiderman I misunderstood your comments, actually I just read a text realating "erasing bit has to consume energy" in Kolmogorov complexity and its application by  Viatanyi and Li. I think I have not read any other relating articles and books  

---

## 1 answers

### Answer by username_2 on 2018-02-02. Score: 21 | Accepted answer

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there is an important difference between *energy* needed to make a computation run, and *entropy* generated by the computation and put out into the environment, typically in the form of heat.)

Based on Landauer and Bennett's original analysis that erasing a bit "must" generate $kT \ln(2)$ entropy (see below for why there are scare-quotes), several researchers have pursued various questions along these lines. One line of research was to simulate irreversible Turing machines by reversible ones, which, it was suggested, would generate no entropy. There are several works showing space-time tradeoffs for how to simulate irreversible TMs by reversible ones, e.g.:

> * Bennett, [Time/Space Trade-Offs for Reversible Computation](https://doi.org/10.1137/0218053). SICOMP 1989
> * Levine & Sherman. [A Note on Bennett’s Time-Space Tradeoff for Reversible Computation](https://doi.org/10.1137/0219046). SICOMP 1990.
> * Li & Vitanyi. [Reversible simulation of irreversible computation](https://doi.org/10.1109/CCC.1996.507692). CCC 1996
> * Lange, McKenzie, and Tapp. [Reversible Space Equals Deterministic Space](https://doi.org/10.1006/jcss.1999.1672). JCSS 2000.

More recently,

> Demaine, Lynch, Mirano, and Tyagi. [Energy-Efficient Algorithms](https://arxiv.org/abs/1605.08448), 2016.

studied partially reversible algorithms - that is, if you are willing to pay some entropy, for standard algorithmic tasks can one improve upon the general irreversible-to-reversible simulations mentioned above. Reversible computing has a whole community of researchers devoted to it, viz. the [Reversible Computing](http://www.reversible-computation.org/) conference, now in its 10th year.

It has actually been known for a long time, going all the way back to Landauer and Bennett, that the relationship between computational irreversibility and entropy generation is more subtle than is suggested by the tagline "erasing a bit generates $\ln(2)$ entropy." However, in the past 20 years or so nonequilibrium statistical mechanics has advanced to the point that this more subtle relationship can be captured by precise numerical equations involving not just entropy difference, but also a difference of KL divergences, see

> Kolchinsky & Wolpert, [Dependence of dissipation on the initial distribution over states](https://dx.doi.org/10.1088/1742-5468/aa7ee1). J. Stat. Mech. 2017 ([arXiv link](https://arxiv.org/abs/1607.00956))

(and references therein).

We hosted a [workshop on this at the Santa Fe Institute](https://www.santafe.edu/events/thermodynamics-and-computation-towards-new-synthes) in August 2017 (where you can see the names of some researchers and talk titles of relevance), and it raises a whole new set of questions in both physics and thermodynamic computational complexity.

> **Comments:**
> **username_0**: Turing Machine or Church-Turing Thesis may be ruled or restricted by physical law, so the possibility whether quantum computation or quantum communication can be implemented may be deduced from physics law, like the second law of  statistical mechanics, general relativity. So I guess if there is any result about the linkage of the thesis and physics law  
> **username_0**: And it seems that physics site is not interested in the topics of this kind.  
> **username_2**: @XL_at_China: There is a "Physical Church-Turing thesis", but this has little to do with the second law, since both the Church-Turing thesis and its physical version are just about what is computable, not about any kind of quantitative estimates, but the second law is a quantitative statement. Also, while there may not have yet been a ton of publications on it, at our workshop the physicists definitely seemed interested.  
> **username_0**: I had tried to find the linkage several years ago,  but failed to get any result. Intuitively, the computability seems  to have to be  linked to the second thermodynamic law. And considering Turing Machine in the term of general relativity, the problem becomes interesting. But I do not know any physicists are interested in such a problem.  
> **username_0**: And could we post a related question on physics of the site, and discuss it with physicist?  
> **username_0**: Having not read the papers you posted as reference， I have known the topics of the field eventually  

---

