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.