Reversible computing: Difference between revisions

Revision as of 07:16, 28 May 2025

Latest revision as of 19:02, 27 June 2025

(One intermediate revision by one other user 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 43:

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