Reversible Space Equals Deterministic Sp
β
Klaus-JΓΆrn Lange; Pierre McKenzie; Alain Tapp
π
Article
π
2000
π
Elsevier Science
π
English
β 168 KB
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 Bennett in 1989 and refutes the conjecture, made by Li and Vitanyi in 1996, that any reversible simulation of an irrev