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

Datalogisk Institut

7 Citationer (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.

Originalsprog	Engelsk
Titel	Reversible computation : 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings
Redaktører	Jean Krivine, Jean-Bernard Stefani
Antal sider	16
Forlag	Springer
Publikationsdato	2015
Sider	29-44
Kapitel	2
ISBN (Trykt)	978-3-319-20859-6
ISBN (Elektronisk)	978-3-319-20860-2
DOI	https://doi.org/10.1007/978-3-319-20860-2_2
Status	Udgivet - 2015
Begivenhed	International Conference, RC 2015 - Grenoble, Frankrig Varighed: 16 jul. 2015 → 17 jul. 2015 Konferencens nummer: 7

Konference

Konference	International Conference, RC 2015
Nummer	7
Land/Område	Frankrig
By	Grenoble
Periode	16/07/2015 → 17/07/2015

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

Emneord

Reversible Turing machines
Structural computational complexity
Time hierarchies
Fast computations
Real time vs. linear time

Adgang til dokumentet

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

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

Citationsformater

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. red. / Jean Krivine; Jean-Bernard Stefani. Springer, 2015. s. 29-44 (Lecture notes in computer science, Bind 9138).

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

Axelsen, HB, Jakobi, S, Kutrib, M & Malcher, A 2015, A hierarchy of fast reversible turing machines. i J Krivine & J-B Stefani (red), Reversible computation: 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings. Springer, Lecture notes in computer science, bind 9138, s. 29-44, International Conference, RC 2015, Grenoble, Frankrig, 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

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater