A hierarchy of fast reversible turing machines

Holger Bock Axelsen; Sebastian Jakobi; Martin Kutrib; Andreas Malcher

doi:10.1007/978-3-319-20860-2_2

A hierarchy of fast reversible turing machines

Holger Bock Axelsen, Sebastian Jakobi, Martin Kutrib, Andreas Malcher

Department of Computer Science

7 Citations (Scopus)

Abstract

Reversible Turing machines with a working tape and a one way or two-way read-only input tape are considered. We investigate the classes of languages acceptable by such devices with small time bounds in the range between real time and linear time, i.e., time bounds of the form n+r(n) where r ∈ o(n) is a sublinear function. It is shown that there exist infinite time hierarchies of separated complexity classes in that range. We then turn to the question of whether reversible Turing machines in the range of interest are weaker than general ones or not. This is answered in the affirmative by proving that there are languages accepted by irreversible one-way Turing machines in real time that cannot be accepted by any reversible one-way machine in less than linear time.

Original language	English
Title of host publication	Reversible computation : 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings
Editors	Jean Krivine, Jean-Bernard Stefani
Number of pages	16
Publisher	Springer
Publication date	2015
Pages	29-44
Chapter	2
ISBN (Print)	978-3-319-20859-6
ISBN (Electronic)	978-3-319-20860-2
DOIs	https://doi.org/10.1007/978-3-319-20860-2_2
Publication status	Published - 2015
Event	International Conference, RC 2015 - Grenoble, France Duration: 16 Jul 2015 → 17 Jul 2015 Conference number: 7

Conference

Conference	International Conference, RC 2015
Number	7
Country/Territory	France
City	Grenoble
Period	16/07/2015 → 17/07/2015

Series	Lecture notes in computer science
Volume	9138
ISSN	0302-9743

Access to Document

10.1007/978-3-319-20860-2_2

http://dx.doi.org/10.1007/978-3-319-20860-2_2

Cite this

Axelsen, H. B., Jakobi, S., Kutrib, M., & Malcher, A. (2015). A hierarchy of fast reversible turing machines. In J. Krivine, & J-B. Stefani (Eds.), Reversible computation: 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings (pp. 29-44). Springer. Lecture notes in computer science Vol. 9138 https://doi.org/10.1007/978-3-319-20860-2_2

A hierarchy of fast reversible turing machines. / Axelsen, Holger Bock; Jakobi, Sebastian; Kutrib, Martin et al.

Reversible computation: 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings. ed. / Jean Krivine; Jean-Bernard Stefani. Springer, 2015. p. 29-44 (Lecture notes in computer science, Vol. 9138).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Axelsen, HB, Jakobi, S, Kutrib, M & Malcher, A 2015, A hierarchy of fast reversible turing machines. in J Krivine & J-B Stefani (eds), Reversible computation: 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings. Springer, Lecture notes in computer science, vol. 9138, pp. 29-44, International Conference, RC 2015, Grenoble, France, 16/07/2015. https://doi.org/10.1007/978-3-319-20860-2_2

@inproceedings{3b898582938b4e8a8fff27d715bbaee1,

title = "A hierarchy of fast reversible turing machines",

abstract = "Reversible Turing machines with a working tape and a one way or two-way read-only input tape are considered. We investigate the classes of languages acceptable by such devices with small time bounds in the range between real time and linear time, i.e., time bounds of the form n+r(n) where r ∈ o(n) is a sublinear function. It is shown that there exist infinite time hierarchies of separated complexity classes in that range. We then turn to the question of whether reversible Turing machines in the range of interest are weaker than general ones or not. This is answered in the affirmative by proving that there are languages accepted by irreversible one-way Turing machines in real time that cannot be accepted by any reversible one-way machine in less than linear time.",

keywords = "Reversible Turing machines, Structural computational complexity, Time hierarchies, Fast computations, Real time vs. linear time",

author = "Axelsen, {Holger Bock} and Sebastian Jakobi and Martin Kutrib and Andreas Malcher",

year = "2015",

doi = "10.1007/978-3-319-20860-2_2",

language = "English",

isbn = "978-3-319-20859-6",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "29--44",

editor = "Jean Krivine and Jean-Bernard Stefani",

booktitle = "Reversible computation",

note = "International Conference, RC 2015 ; Conference date: 16-07-2015 Through 17-07-2015",

}

TY - GEN

T1 - A hierarchy of fast reversible turing machines

AU - Axelsen, Holger Bock

AU - Jakobi, Sebastian

AU - Kutrib, Martin

AU - Malcher, Andreas

N1 - Conference code: 7

PY - 2015

Y1 - 2015

N2 - Reversible Turing machines with a working tape and a one way or two-way read-only input tape are considered. We investigate the classes of languages acceptable by such devices with small time bounds in the range between real time and linear time, i.e., time bounds of the form n+r(n) where r ∈ o(n) is a sublinear function. It is shown that there exist infinite time hierarchies of separated complexity classes in that range. We then turn to the question of whether reversible Turing machines in the range of interest are weaker than general ones or not. This is answered in the affirmative by proving that there are languages accepted by irreversible one-way Turing machines in real time that cannot be accepted by any reversible one-way machine in less than linear time.

AB - Reversible Turing machines with a working tape and a one way or two-way read-only input tape are considered. We investigate the classes of languages acceptable by such devices with small time bounds in the range between real time and linear time, i.e., time bounds of the form n+r(n) where r ∈ o(n) is a sublinear function. It is shown that there exist infinite time hierarchies of separated complexity classes in that range. We then turn to the question of whether reversible Turing machines in the range of interest are weaker than general ones or not. This is answered in the affirmative by proving that there are languages accepted by irreversible one-way Turing machines in real time that cannot be accepted by any reversible one-way machine in less than linear time.

KW - Reversible Turing machines

KW - Structural computational complexity

KW - Time hierarchies

KW - Fast computations

KW - Real time vs. linear time

U2 - 10.1007/978-3-319-20860-2_2

DO - 10.1007/978-3-319-20860-2_2

M3 - Article in proceedings

SN - 978-3-319-20859-6

T3 - Lecture notes in computer science

SP - 29

EP - 44

BT - Reversible computation

A2 - Krivine, Jean

A2 - Stefani, Jean-Bernard

PB - Springer

T2 - International Conference, RC 2015

Y2 - 16 July 2015 through 17 July 2015

ER -

A hierarchy of fast reversible turing machines

Abstract

Conference

Access to Document

Fingerprint

Cite this