Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
A Hierarchy of Fast Reversible Turing Machines
verfasst von : Holger Bock Axelsen, Sebastian Jakobi, Martin Kutrib, Andreas Malcher
Erschienen in: Reversible Computation
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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)$$
n
+
r
(
n
)
where
$$r\in o(n)$$
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.