Reversible space equals deterministic space
K.-J. Lange, Pierre McKenzie, Alain Tapp · 2002
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.