A simple and efficient universal reversible Turing machine

Holger Bock Axelsen; Robert Glück

doi:10.1007/978-3-642-21254-3_8

A simple and efficient universal reversible Turing machine

Holger Bock Axelsen, Robert Glück

Datalogisk Institut

17 Citationer (Scopus)

Abstract

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.

Originalsprog	Engelsk
Titel	Language and Automata Theory and Applications : 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings
Redaktører	Adrian-Horia Dediu, Shunsuke Inenaga, Carlos Martín-Vide
Antal sider	12
Forlag	Springer
Publikationsdato	2011
Sider	117-128
ISBN (Trykt)	978-3-642-21253-6
ISBN (Elektronisk)	978-3-642-21254-3
DOI	https://doi.org/10.1007/978-3-642-21254-3_8
Status	Udgivet - 2011
Begivenhed	5th International Conference on Language and Automata Theory and Applications - Tarragona, Spanien Varighed: 26 maj 2011 → 31 maj 2011 Konferencens nummer: 5

Konference

Konference	5th International Conference on Language and Automata Theory and Applications
Nummer	5
Land/Område	Spanien
By	Tarragona
Periode	26/05/2011 → 31/05/2011

Navn	Lecture notes in computer science
Vol/bind	6638
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-642-21254-3_8

Citationsformater

Axelsen, H. B., & Glück, R. (2011). A simple and efficient universal reversible Turing machine. I A-H. Dediu, S. Inenaga, & C. Martín-Vide (red.), Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings (s. 117-128). Springer. Lecture notes in computer science Bind 6638 https://doi.org/10.1007/978-3-642-21254-3_8

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. red. / Adrian-Horia Dediu; Shunsuke Inenaga; Carlos Martín-Vide. Springer, 2011. s. 117-128 (Lecture notes in computer science, Bind 6638).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Axelsen, HB & Glück, R 2011, A simple and efficient universal reversible Turing machine. i A-H Dediu, S Inenaga & C Martín-Vide (red), Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings. Springer, Lecture notes in computer science, bind 6638, s. 117-128, 5th International Conference on Language and Automata Theory and Applications, Tarragona, Spanien, 26/05/2011. https://doi.org/10.1007/978-3-642-21254-3_8

Axelsen HB, Glück R. A simple and efficient universal reversible Turing machine. I Dediu A-H, Inenaga S, Martín-Vide C, red., Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings. Springer. 2011. s. 117-128. (Lecture notes in computer science, Bind 6638). doi: 10.1007/978-3-642-21254-3_8

Axelsen, Holger Bock ; Glück, Robert. / A simple and efficient universal reversible Turing machine. Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings. red. / Adrian-Horia Dediu ; Shunsuke Inenaga ; Carlos Martín-Vide. Springer, 2011. s. 117-128 (Lecture notes in computer science, Bind 6638).

@inproceedings{3fef687443f84b77bd11a3dffe7d69e9,

title = "A simple and efficient universal reversible Turing machine",

abstract = "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.",

author = "Axelsen, {Holger Bock} and Robert Gl{\"u}ck",

year = "2011",

doi = "10.1007/978-3-642-21254-3_8",

language = "English",

isbn = "978-3-642-21253-6",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "117--128",

editor = "Adrian-Horia Dediu and Shunsuke Inenaga and Carlos Mart{\'i}n-Vide",

booktitle = "Language and Automata Theory and Applications",

note = "5th International Conference on Language and Automata Theory and Applications, LATA 2011 ; Conference date: 26-05-2011 Through 31-05-2011",

}

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 -

A simple and efficient universal reversible Turing machine

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater