DocumentCode
2930447
Title
Reversible space equals deterministic space
Author
Lange, Klaus-Jörn ; Mckenzie, Pierre ; Tapp, Alain
Author_Institution
Wilhelm-Schickard-Inst. fur Inf., Tubingen Univ., Germany
fYear
1997
fDate
24-27 Jun 1997
Firstpage
45
Lastpage
50
Abstract
This paper describes the simulation of an S(n) space-bounded deterministic Turing machine by a reversible Turing machine operating in space S(n). It thus answers a question posed by C. Bennett (1989) and refutes the conjecture, made by M. Li and P. Vitanyi (1996), that any reversible simulation of an irreversible computation must obey Bennett´s reversible pebble game rules
Keywords
Turing machines; deterministic space; irreversible computation; reversible Turing machine; reversible pebble game rules; reversible simulation; reversible space; simulation; space-bounded deterministic Turing machine; Algorithm design and analysis; Circuit simulation; Computational complexity; Computational modeling; Performance analysis; Physics computing; Polynomials; Quantum computing; Thermodynamics; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 1997. Proceedings., Twelfth Annual IEEE Conference on (Formerly: Structure in Complexity Theory Conference)
Conference_Location
Ulm
ISSN
1093-0159
Print_ISBN
0-8186-7907-7
Type
conf
DOI
10.1109/CCC.1997.612299
Filename
612299
Link To Document