Content deleted Content added
m v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation) |
Cnwilliams (talk | contribs) m v2.05 - Repaired 1 link to disambiguation page - (You can help) - Charles H. Bennett |
||
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.
| |||