Reversible Space Equals Deterministic Space

✍ Scribed by Klaus-Jörn Lange; Pierre McKenzie; Alain Tapp

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 168 KB
• Volume: 60
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1672

✦ Synopsis

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 irreversible computation must obey Bennett's reversible pebble game rules. 2000