Content deleted Content added
Tom.Reding (talk | contribs) m +{{Authority control}} (3 IDs from Wikidata); WP:GenFixes & cleanup on |
mNo edit summary |
||
(17 intermediate revisions by 15 users not shown) | |||
Line 1:
{{short description|Model of computation in which all processes are time-reversible}}
'''Reversible computing''' is any [[model of computation]] where every step of the [[computational process|process]]
==Reversibility<!--'Logical reversibility', 'Charge recovery logic', and 'Adiabatic computing' redirect here-->==
Line 10 ⟶ 8:
A process is said to be ''physically reversible'' if it results in no increase in physical [[entropy]]; it is [[isentropic]]. There is a style of circuit design ideally exhibiting this property that is referred to as '''charge recovery logic'''<!--boldface per WP:R#PLA-->, [[adiabatic circuit]]s, or '''adiabatic computing'''<!--boldface per WP:R#PLA--> (see [[Adiabatic process]]). Although ''in practice'' no nonstationary physical process can be ''exactly'' physically reversible or isentropic, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well isolated from interactions with unknown external environments, when the [[Physics|laws of physics]] describing the system's evolution are precisely known.
A motivation for the study of technologies aimed at implementing reversible computing is that they offer what is predicted to be the only potential way to improve the computational [[Efficient energy use|energy efficiency]] (i.e., useful operations performed per unit energy dissipated) of computers beyond the fundamental [[von Neumann-Landauer limit|von Neumann–Landauer limit]]<ref name="landauer">{{Citation |author=Landauer |first=Rolf |title=Irreversibility and heat generation in the computing process |url=http://worrydream.com/refs/Landauer%20-%20Irreversibility%20and%20Heat%20Generation%20in%20the%20Computing%20Process.pdf |journal=IBM Journal of Research and Development |volume=5 |issue=3 |pages=183–191 |year=1961 |doi=10.1147/rd.53.0183 |quote=The entropy of a closed system, e.g., a computer with its own batteries, cannot decrease; hence this entropy must appear elsewhere as a heating effect, supplying 0.6931 kT per restored bit to the surroundings. |accessdate=2015-02-18}}</ref><ref name="neumann">{{cite book|author=J. von Neumann|author-link=John von Neumann|publisher=University of Illinois Press|title=Theory of self-reproducing automata|year=1966|url=https://archive.org/details/theoryofselfrepr00vonn_0|access-date=2022-05-21}} Third lecture: Statistical Theories about Information</ref> of {{Math|''[[kT (energy)|kT]]'' ln(2)}} energy dissipated per irreversible [[bit operation]]. Although the Landauer limit was millions of times below the energy consumption of computers in the 2000s and thousands of times less in the 2010s,<ref>{{cite journal |last1=Bérut |first1=Antoine |last2=Arakelyan |first2=Artak |last3=Petrosyan |first3=Artyom |last4=Ciliberto |first4=Sergio |last5=Dillenschneider |first5=Raoul |last6=Lutz |first6=Eric |title=Experimental verification of Landauer's principle linking information and thermodynamics |journal=Nature |date=March 2012 |volume=483 |issue=7388 |pages=187–189 |doi=10.1038/nature10872 |pmid=22398556 |bibcode=2012Natur.483..187B |arxiv=1503.06537 |s2cid=9415026 }}</ref> proponents of reversible computing argue that this can be attributed largely to architectural overheads which effectively magnify the impact of Landauer's limit in practical circuit designs, so that it may prove difficult for practical technology to progress very far beyond current levels of energy efficiency if reversible computing principles are not used.<ref>Michael P. Frank. Foundations of Generalized Reversible Computing. Conference on Reversible Computation, July 6–7, 2017, Kolkata, India. [[doi:10.1007/978-3-319-59936-6 2]] Preprint available at https://www.osti.gov/servlets/purl/1456440 (PDF).</ref>
==Relation to thermodynamics==
As was first argued by [[Rolf Landauer]] while working at [[IBM]],<ref>{{cite journal |last1=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
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.
Line 26 ⟶ 24:
Today, the field has a substantial body of academic literature. A wide variety of reversible device concepts, [[logic gate]]s, [[electronic circuit]]s, processor architectures, [[programming language]]s, and application [[algorithm]]s have been designed and analyzed by [[physicist]]s, [[electrical engineer]]s, and [[computer scientist]]s.
This field of research awaits the detailed development of a high-quality, cost-effective, nearly reversible logic device technology, one that includes highly energy-efficient [[clocking]] and [[synchronization]] mechanisms, or avoids the need for these through asynchronous design. This sort of solid engineering progress will be needed before the large body of theoretical research on reversible computing can find practical application in enabling real computer technology to circumvent the various near-term barriers to its energy efficiency, including the von Neumann–Landauer bound. This may only be circumvented by the use of logically reversible computing, due to the [[
==Logical reversibility==
Line 35 ⟶ 33:
The [[exclusive or]] (XOR) gate is irreversible because its two inputs cannot be unambiguously reconstructed from its single output, or alternatively, because information erasure is not reversible. However, a reversible version of the XOR gate—the [[controlled NOT gate]] (CNOT)—can be defined by preserving one of the inputs as a 2nd output. The three-input variant of the CNOT gate is called the [[Toffoli gate]]. It preserves two of its inputs ''a,b'' and replaces the third ''c'' by <math>c\oplus (a\cdot b)</math>. With <math>c=0</math>, this gives the AND function, and with <math>a\cdot b=1</math> this gives the NOT function. Because AND and NOT together is a [[functional completeness|functionally complete]] set, the Toffoli gate is universal and can implement any [[Boolean function]] (if given enough initialized [[ancilla bit]]s).
Surveys of reversible circuits, their construction and optimization, as well as recent research challenges, are available.<ref>Rolf Drechsler, Robert Wille. From Truth Tables to Programming Languages: Progress in the Design of Reversible Circuits. International Symposium on Multiple-Valued Logic, 2011. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf</ref><ref>{{cite journal |last1=Saeedi |first1=Mehdi |last2=Markov |first2=Igor L. |title=Synthesis and optimization of reversible circuits—a survey |journal=ACM Computing Surveys |date=1 February 2013 |volume=45 |issue=2 |pages=1–34 |doi=10.1145/2431211.2431220 |arxiv=1110.2574 |s2cid=6302811 }}</ref><ref>Rolf Drechsler and Robert Wille. Reversible Circuits: Recent Accomplishments and Future Challenges for an Emerging Technology. International Symposium on VLSI Design and Test, 2012. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf</ref><ref>{{cite journal |last1=Cohen |first1=Eyal |last2=Dolev |first2=Shlomi |last3=Rosenblit |first3=Michael |title=All-optical design for inherently energy-conserving reversible gates and circuits |journal=Nature Communications |date=26 April 2016 |volume=7 |issue=1 |pages=11424 |doi=10.1038/ncomms11424 |pmid=27113510 |pmc=4853429 |bibcode=2016NatCo...711424C }}</ref><ref>{{Cite journal|last1 =Ang|first1 = Y. S.|last2 = Yang|first2 = S. A.|last3 = Zhang|first3 = C.|last4 = Ma|first4 = Z. S.|last5 = Ang|first5 = L. K.|date = 2017|title = Valleytronics in merging Dirac cones: All-electric-controlled valley filter, valve, and universal reversible logic gate|journal = Physical Review B|volume = 96|issue = 24|pages = 245410|doi = 10.1103/PhysRevB.96.245410|arxiv = 1711.05906|bibcode = 2017PhRvB..96x5410A| s2cid=51933139 }}</ref>▼
== Reversible Turing Machines (RTMs) ==
The Reversible Turing Machine (RTM) is a foundational model in reversible computing. An RTM is defined as a [[Turing machine]] whose transition function is invertible, ensuring that each machine configuration (state and tape content) has at most one predecessor configuration. This guarantees backward determinism, allowing the computation history to be traced uniquely.<ref>{{cite web |url=https://scispace.com/pdf/what-do-reversible-programs-compute-uwj26erp4f.pdf |title=What do reversible programs compute? |website=SciSpace |access-date=April 26, 2025}}</ref>
▲Surveys of reversible circuits, their construction and optimization, as well as recent research challenges, are available.<ref>Rolf Drechsler, Robert Wille. From Truth Tables to Programming Languages: Progress in the Design of Reversible Circuits. International Symposium on Multiple-Valued Logic, 2011. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf</ref><ref>{{cite journal |last1=Saeedi |first1=Mehdi |last2=Markov |first2=Igor L. |title=Synthesis and optimization of reversible circuits—a survey |journal=ACM Computing Surveys |date=1 February 2013 |volume=45 |issue=2 |pages=1–34 |doi=10.1145/2431211.2431220 |arxiv=1110.2574 |s2cid=6302811 }}</ref><ref>Rolf Drechsler and Robert Wille. Reversible Circuits: Recent Accomplishments and Future Challenges for an Emerging Technology. International Symposium on VLSI Design and Test, 2012. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf</ref><ref>{{cite journal |last1=Cohen |first1=Eyal |last2=Dolev |first2=Shlomi |last3=Rosenblit |first3=Michael |title=All-optical design for inherently energy-conserving reversible gates and circuits |journal=Nature Communications |date=26 April 2016 |volume=7 |issue=1 |pages=11424 |doi=10.1038/ncomms11424 |pmid=27113510 |pmc=4853429 |bibcode=2016NatCo...711424C }}</ref><ref>{{Cite journal|last1 =Ang|first1 = Y. S.|last2 = Yang|first2 = S. A.|last3 = Zhang|first3 = C.|last4 = Ma|first4 = Z. S.|last5 = Ang|first5 = L. K.|date = 2017|title = Valleytronics in merging Dirac cones: All-electric-controlled valley filter, valve, and universal reversible logic gate|journal = Physical Review B|volume = 96|issue = 24|pages = 245410|doi = 10.1103/PhysRevB.96.245410|arxiv = 1711.05906|bibcode = 2017PhRvB..96x5410A| s2cid=51933139 }}</ref>
Formal definitions of RTMs have evolved over the last decades. While early definitions focused on invertible transition functions, more general formulations allow for bounded head movement and cell modification per step. This generalization ensures that the set of RTMs is closed under composition (executing one RTM after another results in another RTM) and inversion (the inverse of an RTM is also an RTM), forming a group structure for reversible computations.<ref>{{cite book | arxiv=1603.08715 | doi=10.1007/978-3-319-39300-1_5 | chapter=The Group of Reversible Turing Machines | title=Cellular Automata and Discrete Complex Systems | series=Lecture Notes in Computer Science | date=2016 | last1=Barbieri | first1=Sebastián | last2=Kari | first2=Jarkko | last3=Salo | first3=Ville | volume=9664 | pages=49–62 | isbn=978-3-319-39299-8 }}</ref> This contrasts with some classical TM definitions where composition might not yield a machine of the same class.<ref>{{cite book | arxiv=1603.08715 | doi=10.1007/978-3-319-39300-1_5 | chapter=The Group of Reversible Turing Machines | title=Cellular Automata and Discrete Complex Systems | series=Lecture Notes in Computer Science | date=2016 | last1=Barbieri | first1=Sebastián | last2=Kari | first2=Jarkko | last3=Salo | first3=Ville | volume=9664 | pages=49–62 | isbn=978-3-319-39299-8 }}</ref> The dynamics of an RTM can be described by a global transition function that maps configurations based on a local rule.<ref>{{cite arXiv | eprint=2404.07288 | last1=Bruera | first1=Renzo | last2=Cardona | first2=Robert | last3=Miranda | first3=Eva | last4=Peralta-Salas | first4=Daniel | title=Topological entropy of Turing complete dynamics (With an appendix by Ville Salo) | date=2024 | class=math.DS }}</ref>
[[:fr:Yves Lecerf|Yves Lecerf]] proposed a reversible Turing machine in a 1963 paper,<ref>Lecerf (Y.): [http://vadeker.net/corpus/reversible/lecerf.pdf Logique Mathématique : Machines de Turing réversibles.] Comptes rendus des séances de l'académie des sciences, 257: 2597–2600, 1963.</ref> but apparently unaware of Landauer's principle, did not pursue the subject further, devoting most of the rest of his career to ethnolinguistics.
A landmark result by [[Charles H. Bennett (physicist)|Charles H. Bennett]] in 1973 demonstrated that any standard Turing machine can be simulated by a reversible one.<ref>C. H. Bennett, "[http://www.dna.caltech.edu/courses/cs191/paperscs191/bennett1973.pdf Logical reversibility of computation]", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973</ref> Bennett's construction involves augmenting the TM with an auxiliary "history tape". The simulation proceeds in three stages:<ref>{{cite book | arxiv=2405.20842 | doi=10.1007/978-3-031-62076-8_2 | chapter=Compositional Reversible Computation | title=Reversible Computation | series=Lecture Notes in Computer Science | date=2024 | last1=Carette | first1=Jacques | last2=Heunen | first2=Chris | last3=Kaarsgaard | first3=Robin | last4=Sabry | first4=Amr | volume=14680 | pages=10–27 | isbn=978-3-031-62075-1 }}</ref>
# '''Compute:''' The original TM's computation is simulated, and a record of every transition rule applied is written onto the history tape.
# '''Copy Output:''' The final result on the work tape is copied to a separate, initially blank output tape. This copy operation itself must be done reversibly (e.g., using CNOT gates).
# '''Uncompute:''' The simulation runs in reverse, using the history tape to undo each step of the forward computation. This process erases the work tape and the history tape, returning them to their initial blank state, leaving only the original input (preserved on its tape) and the final output on the output tape.
This construction proves that RTMs are computationally equivalent to standard TMs in terms of the functions they can compute, establishing that reversibility does not limit computational power in this regard.<ref>{{cite book | arxiv=2405.20842 | doi=10.1007/978-3-031-62076-8_2 | chapter=Compositional Reversible Computation | title=Reversible Computation | series=Lecture Notes in Computer Science | date=2024 | last1=Carette | first1=Jacques | last2=Heunen | first2=Chris | last3=Kaarsgaard | first3=Robin | last4=Sabry | first4=Amr | volume=14680 | pages=10–27 | isbn=978-3-031-62075-1 }}</ref> However, this standard simulation technique comes at a cost. The history tape can grow linearly with the computation time, leading to a potentially large space overhead, often expressed as <code>S'(n) = O(S(n)T(n))</code> where S and T are the space and time of the original computation.<ref>C. H. Bennett, "[http://www.dna.caltech.edu/courses/cs191/paperscs191/bennett1973.pdf Logical reversibility of computation]", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973</ref> Furthermore, history-based approaches face challenges with local compositionality; combining two independently reversibilized computations using this method is not straightforward.<ref>{{cite book | arxiv=2405.20842 | doi=10.1007/978-3-031-62076-8_2 | chapter=Compositional Reversible Computation | title=Reversible Computation | series=Lecture Notes in Computer Science | date=2024 | last1=Carette | first1=Jacques | last2=Heunen | first2=Chris | last3=Kaarsgaard | first3=Robin | last4=Sabry | first4=Amr | volume=14680 | pages=10–27 | isbn=978-3-031-62075-1 }}</ref> This indicates that while theoretically powerful, Bennett's original construction is not necessarily the most practical or efficient way to achieve reversible computation, motivating the search for methods that avoid accumulating large amounts of "garbage" history.<ref>{{cite book | arxiv=2405.20842 | doi=10.1007/978-3-031-62076-8_2 | chapter=Compositional Reversible Computation | title=Reversible Computation | series=Lecture Notes in Computer Science | date=2024 | last1=Carette | first1=Jacques | last2=Heunen | first2=Chris | last3=Kaarsgaard | first3=Robin | last4=Sabry | first4=Amr | volume=14680 | pages=10–27 | isbn=978-3-031-62075-1 }}</ref>
RTMs compute precisely the set of injective (one-to-one) computable functions.<ref>{{cite web |url=https://scispace.com/pdf/what-do-reversible-programs-compute-uwj26erp4f.pdf |title=What do reversible programs compute? |website=SciSpace |access-date=April 26, 2025}}</ref> They are not strictly universal in the classical sense because they cannot directly compute non-injective functions (which inherently lose information). However, they possess a form of universality termed "RTM-universality" and are capable of self-interpretation.<ref>{{cite web |url=https://scispace.com/pdf/what-do-reversible-programs-compute-uwj26erp4f.pdf |title=What do reversible programs compute? |website=SciSpace |access-date=April 26, 2025}}</ref>
==Commercialization==
[[London]]-based Vaire Computing is prototyping a chip in 2025, for release in 2027.<ref>{{cite journal |last1=Genkina |first1=Dina |last2=Potter |first2=Ned |last3=Ulrich |first3=Lawrence |last4=Bourzac |first4=Katherine |date=2025-01-01 |title=Reversible Computing Escapes the Lab: Startup Plans the First Chip Based on this Peculiar Power-Saving Scheme |url=https://spectrum.ieee.org/reversible-computing |journal=[[IEEE Spectrum]] |volume=62 |issue=1 |publisher=[[IEEE]] |pages=32–41 |doi=10.1109/MSPEC.2025.10829737}}</ref>
==See also==
Line 68 ⟶ 83:
==Further reading==
* Frank, Michael P. (2017). [https://spectrum.ieee.org/the-future-of-computing-depends-on-making-it-reversible "The Future of Computing Depends on Making It Reversible"]" (web) / "Throwing Computing Into Reverse" (print). ''IEEE'' ''Spectrum''. '''54''' (9): 32–37. [[doi:10.1109/MSPEC.2017.8012237]].
* {{cite journal |last1=Denning |first1=Peter |last2=Lewis |first2=Ted |title=Computers That Can Run Backwards |journal=American Scientist |date=2017 |volume=105 |issue=5 |pages=270 |doi=10.1511/2017.105.5.270 |s2cid=125446656|hdl=10945/59278 |hdl-access=free }}
* {{cite journal |last1=Glück |first1=Robert |last2=Yokoyama |first2=Tetsuo |title=Reversible computing from a programming language perspective |journal=Theoretical Computer Science |date=2023 |volume=953 |pages=113429 |doi=10.1016/j.tcs.2022.06.010 |doi-access=free }}
* {{cite journal |last1=Lange |first1=Klaus-Jörn |last2=McKenzie |first2=Pierre |last3=Tapp |first3=Alain |title=Reversible Space Equals Deterministic Space |journal=Journal of Computer and System Sciences |date=April 2000 |volume=60 |issue=2 |pages=354–367 |doi=10.1006/jcss.1999.1672 |doi-access=free }}
* Perumalla K. S. (2014), ''Introduction to Reversible Computing'', [[CRC Press]].
* {{cite book |doi=10.1145/1062261.1062335 |chapter=Time, space, and energy in reversible computing |title=Proceedings of the 2nd conference on Computing frontiers – CF '05 |year=2005 |last1=Vitányi |first1=Paul |pages=435–444 |arxiv=cs/0504088 |isbn=1595930191 |s2cid=5252384}}
==External links==
|