Time Complexity of Tape Reduction for Reversible Turing Machines

DOI10.1007/978-3-642-29517-1_1zbMath1451.68120OpenAlexW143281069MaRDI QIDQ2902496

Holger Bock Axelsen

Publication date: 20 August 2012

Published in: Reversible Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-29517-1_1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items

On reversible Turing machines and their function universality, A Hierarchy of Fast Reversible Turing Machines