<p>There aren't energy complexity classes yet, but there there's definitely a lot of interest in studying how to design algorithms that are energy efficient under some model. I'm not familiar with the entire body of work, but one entry point is the work that <a href="http://www.cs.pitt.edu/~kirk/">Kirk Pruhs</a> is doing on sustainable computing. Kirk is a theoretician with expertise in scheduling and approximations, and has recently become very active in this area, so his perspective is a good one for algorithmic folks. </p>

<p>p.s gabgoh's point about Landauer's principle is a good one. If you want to learn more about the relation between energy and information, there's no better source than the <a href="http://rads.stackoverflow.com/amzn/click/0691087261">Maxwell's Demon book</a>.</p>

CC BY-SA 2.5
2011-01-09T18:13:14.960Z
2011-01-09T18:13:14.960Z
Suresh Venkat
<p>This isn't a direct answer at all, but are some potentially useful connections to draw/research programmes to be conducted along the lines of Stay and Baez' work on algorithmic thermodynamics: <a href="http://johncarlosbaez.wordpress.com/2010/10/12/algorithmic-thermodynamics/">http://johncarlosbaez.wordpress.com/2010/10/12/algorithmic-thermodynamics/</a></p>

<p>Do take note, however, that this work does not draw out actual physical consequences -- rather it illustrates a connection that is, thus far, purely mathematical.</p>

CC BY-SA 2.5
2011-01-09T18:03:38.467Z
2011-01-09T18:03:38.467Z
sclv
<p>There is some justification for using the external memory model as a model of energy-aware computation. Paolo Ferragina discussed this briefly in his invited talk at ESA 2010, but I don't know if there are any published results. The basic idea is that if the number of I/Os dominates computation time, then the energy required for those I/Os will probably dominate total energy consumption.</p>

<p>The <a href="http://scipm.cs.vt.edu/SciPM-ReportToNSF-Web.pdf" rel="nofollow">report</a> of the <a href="http://scipm.cs.vt.edu/" rel="nofollow">First Workshop on the Science of Power Management</a> mainly contained questions and open problems. I don't know what happened at the <a href="http://www.cs.pitt.edu/~kirk/SciPM2/" rel="nofollow">Second Workshop</a>, but the web pages tell that there will be a special issue of Sustainable Computing dedicated to theoretical, mathematical, and algorithmic approaches to sustainable computing. </p>

CC BY-SA 2.5
2011-01-10T07:51:31.277Z
2011-01-10T07:51:31.277Z
Jouni Sirén
<p>Kei Uchizawa and his coauthors study the energy complexity of threshold circuits.  They define it as the maximum number of threshold gates that output 1 over all possible inputs.</p>

<p>Since it's not about Turing machines, this doesn't answer the question.  But, I hope their papers give some ideas.  His webpage contains pointers.  <a href="http://www.nishizeki.ecei.tohoku.ac.jp/nszk/uchizawa/">http://www.nishizeki.ecei.tohoku.ac.jp/nszk/uchizawa/</a></p>

CC BY-SA 2.5
2011-01-09T21:31:39.547Z
2011-01-09T21:31:39.547Z
Yoshio Okamoto
<p>here are some newer/other references/angles on this apparently deep question with ongoing research. as indicated by P.Shor the area so far seems to be waiting on a comprehensive survey, standardization, and and/or unification. there are more abstract/theoretical approaches listed 1st, followed by more applied approaches: energy efficient algorithms, measurement of energy use in mobile for sorting, study of factors in VLSI affecting energy/time complexity.</p>

<ul>
<li><p><a href="http://dl.acm.org/citation.cfm?id=2422470" rel="nofollow">An energy complexity model for algorithms, Swapnoneel Roy Atri Rudra Akshat Verma ITCS 2013</a></p></li>
<li><p><a href="http://delta.cs.cinvestav.mx/~pmejia/power/energy.pdf" rel="nofollow">Towards an energy complexity of computation Alain J. Martin, IPL 2001</a></p></li>
<li><p><a href="http://arxiv.org/abs/1302.6695" rel="nofollow">Complexity vs Energy: Theory of Computation and Theoretical Physics
Yuri I. Manin</a></p></li>
<li><p><a href="http://www.ravijainweb.com/energy/energy-wcnc05.pdf" rel="nofollow">Towards a Model of Energy Complexity for Algorithms
Ravi Jain, David Molnar, Zulfikar Ramzan</a></p></li>
<li><p><a href="http://cacm.acm.org/magazines/2010/5/87271-energy-efficient-algorithms/fulltext" rel="nofollow">Energy-Efficient Algorithms
Susanne Albers</a></p></li>
<li><p>Yao, F.F., Demers, A.J., Shenker, S. A scheduling model for reduced CPU energy. In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (1995), 374–382.</p></li>
<li><p><a href="http://elab.ws/files/publications/rosocm09_energy.pdf" rel="nofollow">Exploring the Energy Consumption of Data Sorting Algorithms in Embedded and Mobile Environments
Christian Bunse Hagen Ho ̈pfner Essam Mansour Suman Roychoudhury</a></p></li>
<li><p><a href="http://www.computer.org/csdl/trans/tc/2012/04/ttc2012040530-abs.html" rel="nofollow">Energy-Time Complexity of Algorithms: Modelling the Trade-offs of CMOS VLSI (2007) by Brad D. Bingham</a></p></li>
</ul>

CC BY-SA 3.0
2013-03-02T15:51:12.783Z
2013-03-02T15:51:12.783Z
vzn
<p>Recent result from Thermodynamics, actually Stochastic Thermodynamics, that relates the thermodynamic cost of running a Turing Machine, and circuit computation. <a href="https://arxiv.org/pdf/1806.04103.pdf" rel="nofollow noreferrer"> Authors Kolchinsky, and Wolpert </a>- they approach the problem of computing thermodynamic cost of running a Turing Machine, and circuits- their technique extends to TMs. By linking Kolgomorov complexity of the input to the compressibility of output they obtain thermodynamic bounds for computation. The difficulty of computing thermodynamic cost (of running a Turing Machine, circuit computation) is clear. By using Stochastic Thermodynamics to achieve computing the cost  they indicate a divergence from Shannon entropy to compressibility, in computing the thermodynamic cost.</p>
<p>Each run of their model Turing Machine has a &quot;heat&quot; associated with it. In their model the random bits in input generate more &quot;heat&quot; vs computable inputs - this makes it consistent with the physical Church Turing thesis. They use techniques from Kolmogorov Complexity, (their &quot;heat&quot; analogues)  to link to their thermodynamic cost of running a Turing Machine. The stochastic thermodynamic cost functions devised in such a way give them  Kolmogorov related results of computation.</p>

CC BY-SA 4.0
2020-09-02T19:20:09.077Z
2020-09-10T17:05:55.707Z
2020-09-10T17:05:55.707Z
user3483902
<p>Time and space complexities are device independent. I don't see a way to make energy-complexity device independent.</p>

<p>If $W$ is work done by a Turing machine to perform one basic step. Then energy complexity becomes number of steps times $W$. $W$ is highly machine dependent. </p>

<p>And, $O(W f(n)) = O(f(n))$.</p>

CC BY-SA 2.5
2011-01-09T17:37:25.540Z
i am down-voting this answer as I think it misses the point. I think there is some theoretical justification for putting a lower bound on the energy consumption of any algorithm based on Landauer's principle. I find the question very sensible.
gabgoh
CC BY-SA 2.5
2011-01-09T19:23:56.677Z
@gabgoh I fear any general lower bound would have to make uniformity assumptions that would defeat the purpose. @TheMachineCharmer In fact, real processors can have different orderings of commands by efficiency. Upvote, althoug your second paragraph confuses me.
Raphael
CC BY-SA 2.5
2011-01-09T21:01:59.700Z
@gabgoh: the guy was called Landau, not Landauer.
Konrad Rudolph
CC BY-SA 2.5
2011-01-10T02:13:30.257Z
Time and space are NOT device-independent in exactly the same way that energy is not device-independent. A single computational step on a 1970 IBM 360 takes a lot longer than a single computational step on my laptop. Theoretically, a reversible computational step should cost $\alpha$ units of energy while a non-reversible computational step should cost $\beta$ units of energy, where the actual values of $\alpha$ and $\beta$ are machine dependent. However, the number of $\alpha$ and $\beta$ steps depends only on the program.
Peter Shor 
CC BY-SA 2.5
2011-01-10T02:15:30.567Z
@Konrad: gabgoh is referring to Rolf Landauer, not Lev Landau.
Peter Shor 
CC BY-SA 2.5
2011-01-10T08:12:37.747Z
@Peter: thanks for the info. For the record though, I was talking about Edmund Landau, inventor of the big-O notation. I thought that was what gabgoh was referring to with “Landauer’s principle”.
Konrad Rudolph
CC BY-SA 2.5
2011-01-10T16:54:04.790Z
@Konrad: I was thinking physicists and not computer scientists. Obviously the wrong strategy for this site.
Peter Shor 
CC BY-SA 2.5
2011-01-09T17:14:02.030Z
2011-01-09T17:14:02.030Z
Pratik Deoghare
<p><em>Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms?</em>  <strong><em>No!</em></strong></p>

<p>But maybe you could come up with one. It's possible you could divide the Turing machine steps into reversible and non-reversible (the non-reversible ones are where information is lost). Theoretically, it is only the non-reversible steps that cost energy. A cost of one unit of energy for each bit that is erased would theoretically be the right measure. </p>

<p>There is a theorem of Charles Bennett that the time complexity increases by at most a constant when a computation is made reversible (C.H. Bennett, <em>Logical Reversibility of Computation</em>), but if there are also limits on space, then making the computational reversible might incur a substantial increase in time <a href="http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&amp;id=SMJCAT000018000004000766000001&amp;idtype=cvips&amp;gifs=yes&amp;ref=no">(Reference here)</a>. Landauer's principle says that erasing a bit costs $kT\, \ln 2$ of energy, where $T$ is temperature and $k$ is Boltzmann's constant. In real life, you cannot come anywhere close to achieving this minimum. However, you can build chips which perform reversible steps using substantially less energy than they use for irreversible steps. If you give reversible steps a cost of $\alpha$ and irreversible steps a cost of $\beta$, this seems like it may give a reasonable theoretical model.</p>

<p>I don't know how Turing machines with some reversible steps relate to chips with some reversible circuitry, but I think both models are worth investigating.</p>

CC BY-SA 2.5
2011-01-10T03:55:06.980Z
Peter, in discussions about Efficient Church-Turing Thesis, I remember reading about taking the amount of energy used in the computation into account. Do you know if there is a good reference on the topic? (I can post this as a separate question if you prefer that.)
Kaveh
CC BY-SA 2.5
2011-01-10T04:13:56.370Z
If you're just worried about polynomial factors, as you are for the Efficient Church-Turing thesis, everything works out, because you can get reversible computation (arbitrarily small amount of energy expended) with only a constant factor increase in time, and the space cannot be any larger than the time. I think I saw a good recent survey about this stuff. Hopefully somebody can locate it.
Peter Shor 
CC BY-SA 2.5
2011-01-10T22:56:48.617Z
Thanks Peter, I guess I might find it myself using Google (I will post a question if I don't find).
Kaveh
CC BY-SA 3.0
2013-03-03T02:11:28.843Z
interesting ideas that lead to the question, how much can arbitrary algorithms be transformed into reversible computations? as in qm computing this is always possible with "ancilla" bits but keeping this "scratch" can decrease the efficiency of the algorithm in some cases and its maybe so far not so well understood how much. note williams has some ideas on [space-efficient reversible computations](http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Williams_SpaceReversible.pdf)
vzn
CC BY-SA 3.0
2017-05-28T16:51:35.940Z
Even if we have a reversible-computation machine, there are still some "hidden" energy costs: When we want to run a new computation, we must either build a new memory bank, or erase some of the previously-written data to make room for the new input and computations. How does this affect the answer? (e.g. does reversible computation usually assume access to a section of initialized, "blank" memory? seems like cheating...)
usul
CC BY-SA 3.0
2017-05-28T17:06:29.560Z
@usul: Reversible computation reversibly re-initializes memory when it finishes using it for workspace. If you want, it can also re-initialize the memory used by the answer, by uncomputing the answer. (But then, unless you've copied the answer to another device, you might as well not have done the computation.)
Peter Shor 
CC BY-SA 3.0
2017-06-12T11:30:53.757Z
And it might be more energy-efficient to erase the workspace rather than uncomputing it, depending on the ratio between the energy cost of reversible and irreversible operations. This can be taken into account by the methods outlined in the answer.
Peter Shor 
CC BY-SA 2.5
2011-01-10T02:09:11.633Z
2011-01-10T04:21:10.150Z
2011-01-10T04:21:10.150Z
Peter Shor 
<p>Computational complexity includes the study of time or space complexity of computational problems. From the the perspective of mobile computing, energy is very valuable computational resource. So, Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms. Also, Are there established energy-complexity classes for computational problems?  </p>

<p>References are appreciated.</p>

CC BY-SA 3.0
2011-09-18T19:04:31.910Z
Susanne Albers wrote an excellent survey in the Communication of ACM, Energy efficient algorithms. http://cacm.acm.org/magazines/2010/5/87271-energy-efficient-algorithms/fulltext
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-11-17T20:34:32.470Z
There is also this recent paper: https://doi.org/10.1103/PhysRevResearch.2.033312
Do you have any update in these past 10 years?
domotorp
CC BY-SA 2.5
2011-01-09T19:26:41.697Z
Energy consumption is machine dependent and a practical issue, i.e. the constants hidden in classical analysis are typically of interest (any the only difference between runtime and energy consumption).
Raphael
CC BY-SA 2.5
2011-01-10T03:36:55.083Z
Theoretically, you can do reversible steps with no energy cost. Practically, one can build chips which perform reversible steps at a substantially lower energy cost than non-reversible steps. How this translates into theory isn't clear, but maybe we can define a Turing machine model which does reversible steps at cost $\alpha$ and non-reversible steps at cost $\beta$, and start reasoning about energy consumption theoretically. At least it's possibly better than throwing up your hands in despair and saying "it's all machine dependent."
Peter Shor 
CC BY-SA 2.5
2011-01-10T03:50:38.590Z
Possible related: [How much computational power fits into a cubic centimeter?](http://cstheory.stackexchange.com/q/2758/186), [DNA-algorithms and NP-completeness](http://cstheory.stackexchange.com/questions/2703/dna-algorithms-and-np-completeness).
Kaveh
<cc.complexity-theory><physics>
Formal notion for energy complexity of computational problems
Mohammad Al-Turkistany
# Formal notion for energy complexity of computational problems

(Asked by: username_0 on 2011-01-09)

Computational complexity includes the study of time or space complexity of computational problems. From the the perspective of mobile computing, energy is very valuable computational resource. So, Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms. Also, Are there established energy-complexity classes for computational problems?

References are appreciated.

**Tags:** cc.complexity-theory, physics
> **Comments:**
> **username_2**: Energy consumption is machine dependent and a practical issue, i.e. the constants hidden in classical analysis are typically of interest (any the only difference between runtime and energy consumption).  
> **username_3**: Theoretically, you can do reversible steps with no energy cost. Practically, one can build chips which perform reversible steps at a substantially lower energy cost than non-reversible steps. How this translates into theory isn't clear, but maybe we can define a Turing machine model which does reversible steps at cost $\alpha$ and non-reversible steps at cost $\beta$, and start reasoning about energy consumption theoretically. At least it's possibly better than throwing up your hands in despair and saying "it's all machine dependent."  
> **username_4**: Possible related: [How much computational power fits into a cubic centimeter?](http://cstheory.stackexchange.com/q/2758/186), [DNA-algorithms and NP-completeness](http://cstheory.stackexchange.com/questions/2703/dna-algorithms-and-np-completeness).  
> **username_0**: Susanne Albers wrote an excellent survey in the Communication of ACM, Energy efficient algorithms. http://cacm.acm.org/magazines/2010/5/87271-energy-efficient-algorithms/fulltext  
> **username_1**: There is also this recent paper: https://doi.org/10.1103/PhysRevResearch.2.033312 Do you have any update in these past 10 years?  

---

## 8 answers

### Answer by username_3 on 2011-01-10. Score: 27 | Accepted answer

*Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms?* ***No!***

But maybe you could come up with one. It's possible you could divide the Turing machine steps into reversible and non-reversible (the non-reversible ones are where information is lost). Theoretically, it is only the non-reversible steps that cost energy. A cost of one unit of energy for each bit that is erased would theoretically be the right measure.

There is a theorem of Charles Bennett that the time complexity increases by at most a constant when a computation is made reversible (C.H. Bennett, *Logical Reversibility of Computation*), but if there are also limits on space, then making the computational reversible might incur a substantial increase in time [(Reference here)](http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000018000004000766000001&idtype=cvips&gifs=yes&ref=no). Landauer's principle says that erasing a bit costs $kT\, \ln 2$ of energy, where $T$ is temperature and $k$ is Boltzmann's constant. In real life, you cannot come anywhere close to achieving this minimum. However, you can build chips which perform reversible steps using substantially less energy than they use for irreversible steps. If you give reversible steps a cost of $\alpha$ and irreversible steps a cost of $\beta$, this seems like it may give a reasonable theoretical model.

I don't know how Turing machines with some reversible steps relate to chips with some reversible circuitry, but I think both models are worth investigating.

> **Comments:**
> **username_4**: Peter, in discussions about Efficient Church-Turing Thesis, I remember reading about taking the amount of energy used in the computation into account. Do you know if there is a good reference on the topic? (I can post this as a separate question if you prefer that.)  
> **username_3**: If you're just worried about polynomial factors, as you are for the Efficient Church-Turing thesis, everything works out, because you can get reversible computation (arbitrarily small amount of energy expended) with only a constant factor increase in time, and the space cannot be any larger than the time. I think I saw a good recent survey about this stuff. Hopefully somebody can locate it.  
> **username_4**: Thanks Peter, I guess I might find it myself using Google (I will post a question if I don't find).  
> **username_9**: interesting ideas that lead to the question, how much can arbitrary algorithms be transformed into reversible computations? as in qm computing this is always possible with "ancilla" bits but keeping this "scratch" can decrease the efficiency of the algorithm in some cases and its maybe so far not so well understood how much. note williams has some ideas on [space-efficient reversible computations](http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Williams_SpaceReversible.pdf)  
> **username_14**: Even if we have a reversible-computation machine, there are still some "hidden" energy costs: When we want to run a new computation, we must either build a new memory bank, or erase some of the previously-written data to make room for the new input and computations. How does this affect the answer? (e.g. does reversible computation usually assume access to a section of initialized, "blank" memory? seems like cheating...)  
> **username_3**: @usul: Reversible computation reversibly re-initializes memory when it finishes using it for workspace. If you want, it can also re-initialize the memory used by the answer, by uncomputing the answer. (But then, unless you've copied the answer to another device, you might as well not have done the computation.)  
> **username_3**: And it might be more energy-efficient to erase the workspace rather than uncomputing it, depending on the ratio between the energy cost of reversible and irreversible operations. This can be taken into account by the methods outlined in the answer.  

---

### Answer by username_5 on 2011-01-09. Score: 8

There aren't energy complexity classes yet, but there there's definitely a lot of interest in studying how to design algorithms that are energy efficient under some model. I'm not familiar with the entire body of work, but one entry point is the work that [Kirk Pruhs](http://www.cs.pitt.edu/~kirk/) is doing on sustainable computing. Kirk is a theoretician with expertise in scheduling and approximations, and has recently become very active in this area, so his perspective is a good one for algorithmic folks.

p.s gabgoh's point about Landauer's principle is a good one. If you want to learn more about the relation between energy and information, there's no better source than the [Maxwell's Demon book](http://rads.stackoverflow.com/amzn/click/0691087261).


---

### Answer by username_6 on 2011-01-09. Score: 5

This isn't a direct answer at all, but are some potentially useful connections to draw/research programmes to be conducted along the lines of Stay and Baez' work on algorithmic thermodynamics: <http://johncarlosbaez.wordpress.com/2010/10/12/algorithmic-thermodynamics/>

Do take note, however, that this work does not draw out actual physical consequences -- rather it illustrates a connection that is, thus far, purely mathematical.


---

### Answer by username_8 on 2011-01-09. Score: 5

Kei Uchizawa and his coauthors study the energy complexity of threshold circuits. They define it as the maximum number of threshold gates that output 1 over all possible inputs.

Since it's not about Turing machines, this doesn't answer the question. But, I hope their papers give some ideas. His webpage contains pointers. <http://www.nishizeki.ecei.tohoku.ac.jp/nszk/uchizawa/>


---

### Answer by username_7 on 2011-01-10. Score: 4

There is some justification for using the external memory model as a model of energy-aware computation. Paolo Ferragina discussed this briefly in his invited talk at ESA 2010, but I don't know if there are any published results. The basic idea is that if the number of I/Os dominates computation time, then the energy required for those I/Os will probably dominate total energy consumption.

The [report](http://scipm.cs.vt.edu/SciPM-ReportToNSF-Web.pdf) of the [First Workshop on the Science of Power Management](http://scipm.cs.vt.edu/) mainly contained questions and open problems. I don't know what happened at the [Second Workshop](http://www.cs.pitt.edu/~kirk/SciPM2/), but the web pages tell that there will be a special issue of Sustainable Computing dedicated to theoretical, mathematical, and algorithmic approaches to sustainable computing.


---

### Answer by username_9 on 2013-03-02. Score: 0

here are some newer/other references/angles on this apparently deep question with ongoing research. as indicated by P.Shor the area so far seems to be waiting on a comprehensive survey, standardization, and and/or unification. there are more abstract/theoretical approaches listed 1st, followed by more applied approaches: energy efficient algorithms, measurement of energy use in mobile for sorting, study of factors in VLSI affecting energy/time complexity.

* [An energy complexity model for algorithms, Swapnoneel Roy Atri Rudra Akshat Verma ITCS 2013](http://dl.acm.org/citation.cfm?id=2422470)
* [Towards an energy complexity of computation Alain J. Martin, IPL 2001](http://delta.cs.cinvestav.mx/~pmejia/power/energy.pdf)
* [Complexity vs Energy: Theory of Computation and Theoretical Physics
  Yuri I. Manin](http://arxiv.org/abs/1302.6695)
* [Towards a Model of Energy Complexity for Algorithms
  Ravi Jain, David Molnar, Zulfikar Ramzan](http://www.ravijainweb.com/energy/energy-wcnc05.pdf)
* [Energy-Efficient Algorithms
  Susanne Albers](http://cacm.acm.org/magazines/2010/5/87271-energy-efficient-algorithms/fulltext)
* Yao, F.F., Demers, A.J., Shenker, S. A scheduling model for reduced CPU energy. In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (1995), 374–382.
* [Exploring the Energy Consumption of Data Sorting Algorithms in Embedded and Mobile Environments
  Christian Bunse Hagen Ho ̈pfner Essam Mansour Suman Roychoudhury](http://elab.ws/files/publications/rosocm09_energy.pdf)
* [Energy-Time Complexity of Algorithms: Modelling the Trade-offs of CMOS VLSI (2007) by Brad D. Bingham](http://www.computer.org/csdl/trans/tc/2012/04/ttc2012040530-abs.html)


---

### Answer by username_10 on 2020-09-02. Score: 0

Recent result from Thermodynamics, actually Stochastic Thermodynamics, that relates the thermodynamic cost of running a Turing Machine, and circuit computation.  [Authors Kolchinsky, and Wolpert](https://arxiv.org/pdf/1806.04103.pdf) - they approach the problem of computing thermodynamic cost of running a Turing Machine, and circuits- their technique extends to TMs. By linking Kolgomorov complexity of the input to the compressibility of output they obtain thermodynamic bounds for computation. The difficulty of computing thermodynamic cost (of running a Turing Machine, circuit computation) is clear. By using Stochastic Thermodynamics to achieve computing the cost they indicate a divergence from Shannon entropy to compressibility, in computing the thermodynamic cost.

Each run of their model Turing Machine has a "heat" associated with it. In their model the random bits in input generate more "heat" vs computable inputs - this makes it consistent with the physical Church Turing thesis. They use techniques from Kolmogorov Complexity, (their "heat" analogues) to link to their thermodynamic cost of running a Turing Machine. The stochastic thermodynamic cost functions devised in such a way give them Kolmogorov related results of computation.


---

### Answer by username_11 on 2011-01-09. Score: -3

Time and space complexities are device independent. I don't see a way to make energy-complexity device independent.

If $W$ is work done by a Turing machine to perform one basic step. Then energy complexity becomes number of steps times $W$. $W$ is highly machine dependent.

And, $O(W f(n)) = O(f(n))$.

> **Comments:**
> **username_12**: i am down-voting this answer as I think it misses the point. I think there is some theoretical justification for putting a lower bound on the energy consumption of any algorithm based on Landauer's principle. I find the question very sensible.  
> **username_2**: @gabgoh I fear any general lower bound would have to make uniformity assumptions that would defeat the purpose. @TheMachineCharmer In fact, real processors can have different orderings of commands by efficiency. Upvote, althoug your second paragraph confuses me.  
> **username_13**: @gabgoh: the guy was called Landau, not Landauer.  
> **username_3**: Time and space are NOT device-independent in exactly the same way that energy is not device-independent. A single computational step on a 1970 IBM 360 takes a lot longer than a single computational step on my laptop. Theoretically, a reversible computational step should cost $\alpha$ units of energy while a non-reversible computational step should cost $\beta$ units of energy, where the actual values of $\alpha$ and $\beta$ are machine dependent. However, the number of $\alpha$ and $\beta$ steps depends only on the program.  
> **username_3**: @Konrad: gabgoh is referring to Rolf Landauer, not Lev Landau.  
> **username_13**: @Peter: thanks for the info. For the record though, I was talking about Edmund Landau, inventor of the big-O notation. I thought that was what gabgoh was referring to with “Landauer’s principle”.  
> **username_3**: @Konrad: I was thinking physicists and not computer scientists. Obviously the wrong strategy for this site.  

---

