Content deleted Content added
Citation bot (talk | contribs) Altered template type. Add: class, eprint, isbn, pages, volume, date, series, title, chapter, doi, arxiv, authors 1-4. Changed bare reference to CS1/2. Removed parameters. Some additions/deletions were parameter name changes. Upgrade ISBN10 to 13. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar |
m The RTM section should link to the Turing Machine page |
||
Line 37:
== 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>.
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>.
| |||