CCC'97
Klaus-Jörn Lange, Pierre McKenzie and Alain Tapp,
Reversible space equals deterministic space,
12th Annual IEEE Conf. on Computational Complexity (CCC'97),
june 1997, pp. 45-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 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.