Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
A Simple and Efficient Universal Reversible Turing Machine
verfasst von : Holger Bock Axelsen, Robert Glück
Erschienen in: Language and Automata Theory and Applications
Verlag: Springer Berlin Heidelberg
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
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.