Forskning ved Københavns Universitet - Københavns Universitet

Forside

A simple and efficient universal reversible Turing machine

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

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.
OriginalsprogEngelsk
TitelLanguage and Automata Theory and Applications : 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings
RedaktørerAdrian-Horia Dediu, Shunsuke Inenaga, Carlos Martín-Vide
Antal sider12
ForlagSpringer
Publikationsdato2011
Sider117-128
ISBN (Trykt)978-3-642-21253-6
ISBN (Elektronisk)978-3-642-21254-3
DOI
StatusUdgivet - 2011
Begivenhed5th International Conference on Language and Automata Theory and Applications - Tarragona, Spanien
Varighed: 26 maj 201131 maj 2011
Konferencens nummer: 5

Konference

Konference5th International Conference on Language and Automata Theory and Applications
Nummer5
LandSpanien
ByTarragona
Periode26/05/201131/05/2011
NavnLecture notes in computer science
Vol/bind6638
ISSN0302-9743

ID: 33055994