A simple and efficient universal reversible Turing machine
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
A simple and efficient universal reversible Turing machine. / Axelsen, Holger Bock; Glück, Robert.
Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings. ed. / Adrian-Horia Dediu; Shunsuke Inenaga; Carlos Martín-Vide. Springer, 2011. p. 117-128 (Lecture notes in computer science, Vol. 6638).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - A simple and efficient universal reversible Turing machine
AU - Axelsen, Holger Bock
AU - Glück, Robert
N1 - Conference code: 5
PY - 2011
Y1 - 2011
N2 - We construct a universal reversible Turing machine (URTM) from first principles. We take a strict approach to the semantics of reversible Turing machines (RTMs), under which they can compute exactly all injective, computable functions, but not non-injective ones. The natural notion of universality for RTMs is RTM-universality, where programs are considered part of both input and output of a URTM.The machine described here is the first URTM which does not depend on reversibilizing any existing universal machine. The interpretive overhead of the URTM is limited to a (program dependent) constant factor slowdown, with no other complexity-wise cost wrt time and space. The URTM is also able to function as an inverse interpreter for RTMs at no asymptotic cost, simply by reversing the string representing the interpreted machine.
AB - We construct a universal reversible Turing machine (URTM) from first principles. We take a strict approach to the semantics of reversible Turing machines (RTMs), under which they can compute exactly all injective, computable functions, but not non-injective ones. The natural notion of universality for RTMs is RTM-universality, where programs are considered part of both input and output of a URTM.The machine described here is the first URTM which does not depend on reversibilizing any existing universal machine. The interpretive overhead of the URTM is limited to a (program dependent) constant factor slowdown, with no other complexity-wise cost wrt time and space. The URTM is also able to function as an inverse interpreter for RTMs at no asymptotic cost, simply by reversing the string representing the interpreted machine.
U2 - 10.1007/978-3-642-21254-3_8
DO - 10.1007/978-3-642-21254-3_8
M3 - Article in proceedings
SN - 978-3-642-21253-6
T3 - Lecture notes in computer science
SP - 117
EP - 128
BT - Language and Automata Theory and Applications
A2 - Dediu, Adrian-Horia
A2 - Inenaga, Shunsuke
A2 - Martín-Vide, Carlos
PB - Springer
T2 - 5th International Conference on Language and Automata Theory and Applications
Y2 - 26 May 2011 through 31 May 2011
ER -
ID: 33055994