Reversible computing: Difference between revisions

Revision as of 21:08, 21 May 2022

Revision as of 21:16, 21 May 2022

Line 13:

==Relation to thermodynamics==

As was first argued by [[Rolf Landauer]] while working at [[IBM]],<ref>{{cite namejournal |last1="landauer"Landauer |first1=R. |title=Irreversibility and Heat Generation in the Computing Process |journal=IBM Journal of Research and Development |date=July 1961 |volume=5 |issue=3 |pages=183–191 |doi=10.1147/rd.53.0183 }}</ref> in order for a computational process to be physically reversible, it must also be ''logically reversible''. [[Landauer's principle]] is the rigorously valid observation that the oblivious erasure of ''n'' bits of known information must always incur a cost of {{Math|''nkT'' ln(2)}} in thermodynamic [[entropy]]. A discrete, deterministic computational process is said to be logically reversible if the transition function that maps old computational states to new ones is a [[one-to-one function]]; i.e. the output logical states uniquely determine the input logical states of the computational operation.

For computational processes that are nondeterministic (in the sense of being probabilistic or random), the relation between old and new states is not a [[single-valued function]], and the requirement needed to obtain physical reversibility becomes a slightly weaker condition, namely that the size of a given ensemble of possible initial computational states does not decrease, on average, as the computation proceeds forwards.