Reversible computing: Difference between revisions

Revision as of 07:47, 19 May 2025

Latest revision as of 19:02, 27 June 2025

(6 intermediate revisions by 6 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]] is [[time-reversible]]. This means that, given the output of a computation, it's is possible to perfectly reconstruct the input. In systems that [[Transition system|progress]] [[Deterministic system|deterministically]] from one state to another, a key requirement for reversibility is a [[injective function|one-to-one]] [[Binary relation|correspondence]] between each state and its successor. Reversible computing is considered an unconventional approach to computation and is closely linked to [[quantum computing]], where the principles of quantum mechanics inherently ensure reversibility (as long as [[quantum state]]s are not measured or "[[wave function collapse|collapsed]]").<ref name="Williams">{{cite book |author=Williams |first=Colin P. |title=Explorations in Quantum Computing |publisher=[[Springer Science+Business Media|Springer]] |year=2011 |isbn=978-1-84628-887-6 |pages=25–29}}</ref>

==Reversibility<!--'Logical reversibility', 'Charge recovery logic', and 'Adiabatic computing' redirect here-->==

Line 35:

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>.

=== Reversible Turing Machines (RTMs) ===

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 webbook |url=https:// arxiv.org/pdf/=1603.08715 |title doi=10.1007/978-3-319-39300-1_5 | chapter=The groupGroup of reversibleReversible Turing machinesMachines |website title=arXivCellular Automata and Discrete Complex Systems |access- series=Lecture Notes in Computer Science | date=April2016 26,| last1=Barbieri | first1=Sebastián | last2=Kari | first2=Jarkko | last3=Salo | first3=Ville | volume=9664 | pages=49–62 | isbn=978-3-319-39299-8 2025}}</ref>. This contrasts with some classical TM definitions where composition might not yield a machine of the same class .<ref>{{cite webbook |url=https:// arxiv.org/pdf/=1603.08715 |title doi=10.1007/978-3-319-39300-1_5 | chapter=The groupGroup of reversibleReversible Turing machinesMachines |website title=arXivCellular Automata and Discrete Complex Systems |access- series=Lecture Notes in Computer Science | date=April2016 26,| last1=Barbieri | first1=Sebastián | last2=Kari | first2=Jarkko | last3=Salo | first3=Ville | volume=9664 | pages=49–62 | isbn=978-3-319-39299-8 2025}}</ref>. The dynamics of an RTM can be described by a global transition function that maps configurations based on a local rule .<ref>{{cite webarXiv |url eprint=https://arxiv.org/pdf/2404.07288 |title last1=TOPOLOGICALBruera ENTROPY| OFfirst1=Renzo TURING| COMPLETElast2=Cardona DYNAMICS| first2=Robert |website last3=arXivMiranda |access first3=Eva | last4=Peralta-Salas | first4=Daniel | title=Topological entropy of Turing complete dynamics (With an appendix by Ville Salo) | date=April2024 26,| class=math.DS 2025}}</ref>.

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>.

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 web |url=https://arxiv.org/pdf/1603.08715 |title=The group of reversible Turing machines |website=arXiv |access-date=April 26, 2025}}</ref>. This contrasts with some classical TM definitions where composition might not yield a machine of the same class <ref>{{cite web |url=https://arxiv.org/pdf/1603.08715 |title=The group of reversible Turing machines |website=arXiv |access-date=April 26, 2025}}</ref>. The dynamics of an RTM can be described by a global transition function that maps configurations based on a local rule <ref>{{cite web |url=https://arxiv.org/pdf/2404.07288 |title=TOPOLOGICAL ENTROPY OF TURING COMPLETE DYNAMICS |website=arXiv |access-date=April 26, 2025}}</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 webbook |url arxiv=https://arxiv.org/html/2405.20842v120842 |title doi=10.1007/978-3-031-62076-8_2 | chapter=Compositional Reversible Computation |website title=arXivReversible Computation |access- series=Lecture Notes in Computer Science | date=April2024 26,| 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 2025}}</ref>:

# '''Compute:''' The original TM's computation is simulated, and a record of every transition rule applied is written onto the history tape.

Line 51 ⟶ 49:

# '''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 webbook |url=https:// arxiv.org/html/=2405.20842v120842 |title doi=10.1007/978-3-031-62076-8_2 | chapter=Compositional Reversible Computation |website title=arXivReversible Computation |access- series=Lecture Notes in Computer Science | date=April2024 26,| 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 2025}}</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 webbook |url=https:// arxiv.org/html/=2405.20842v120842 |title doi=10.1007/978-3-031-62076-8_2 | chapter=Compositional Reversible Computation |website title=arXivReversible Computation |access- series=Lecture Notes in Computer Science | date=April2024 26,| 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 2025}}</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 webbook |url=https:// arxiv.org/html/=2405.20842v120842 |title doi=10.1007/978-3-031-62076-8_2 | chapter=Compositional Reversible Computation |website title=arXivReversible Computation |access- series=Lecture Notes in Computer Science | date=April2024 26,| 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 2025}}</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==

Line 89 ⟶ 87:

* {{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==