Abstract
Reversible computing is the study of computation models that exhibit both forward and backward determinism. Understanding the fundamental properties of such models is not only relevant for reversible programming, but has also been found important in other fields, e.g., bidirectional model transformation, program transformations such as inversion, and general static prediction of program properties.
Historically, work on reversible computing has focussed on reversible simulations of irreversible computations. Here, we take the viewpoint that the property of reversibility itself should be the starting point of a computational theory of reversible computing. We provide a novel semantics-based approach to such a theory, using reversible Turing machines (RTMs) as the underlying computation model.
We show that the RTMs can compute exactly all injective, computable functions. We find that the RTMs are not strictly classically universal, but that they support another notion of universality; we call this RTM-universality. Thus, even though the RTMs are sub-universal in the classical sense, they are powerful enough as to include a self-interpreter. Lifting this to other computation models, we propose r-Turing completeness as the ‘gold standard’ for computability in reversible computation models.
Historically, work on reversible computing has focussed on reversible simulations of irreversible computations. Here, we take the viewpoint that the property of reversibility itself should be the starting point of a computational theory of reversible computing. We provide a novel semantics-based approach to such a theory, using reversible Turing machines (RTMs) as the underlying computation model.
We show that the RTMs can compute exactly all injective, computable functions. We find that the RTMs are not strictly classically universal, but that they support another notion of universality; we call this RTM-universality. Thus, even though the RTMs are sub-universal in the classical sense, they are powerful enough as to include a self-interpreter. Lifting this to other computation models, we propose r-Turing completeness as the ‘gold standard’ for computability in reversible computation models.
| Original language | English |
|---|---|
| Title of host publication | Foundations of Software Science and Computational Structures : 14th International Conference, FOSSACS 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26–April 3, 2011. Proceedings |
| Editors | Martin Hofmann |
| Number of pages | 15 |
| Publisher | Springer |
| Publication date | 2011 |
| Pages | 42-56 |
| ISBN (Print) | 978-3-642-19804-5 |
| ISBN (Electronic) | 978-3-642-19805-2 |
| DOIs | |
| Publication status | Published - 2011 |
| Event | 14th International Conference on Foundations of Software Science and Computational Structures - Saarbrücken, Germany Duration: 26 Mar 2011 → 3 Apr 2011 Conference number: 14 |
Conference
| Conference | 14th International Conference on Foundations of Software Science and Computational Structures |
|---|---|
| Number | 14 |
| Country/Territory | Germany |
| City | Saarbrücken |
| Period | 26/03/2011 → 03/04/2011 |
| Series | Lecture notes in computer science |
|---|---|
| Volume | 6604 |
| ISSN | 0302-9743 |