REVERSIBLE SIMULATION OF SPACE-BOUNDED COMPUTATIONS

We give an alternative proof of Bennett's simulation of deterministic Turing machines by reversible ones (machines whose configuration graph has out-degree and in-degree one) with a quadratic loss of space. Mor e importantly, our proof extends this result to nondeterministic Turin g machines.