Time/Space Trade-Offs for Reversible Computation

A reversible Turing machine is one whose transition function is 1: 1, so that no instantaneous description (ID) has more than one predecessor. Using a pebbling argument, this paper shows that, for any > 0, ordinary multitape Turing machines using time T and space S can be simulated by reversible ones using time O (T^1 +) and space O (S T) or in linear time and space O (ST^). The former result implies in particular that reversible machines can simulate ordinary ones in quadratic space. These results refer to reversible machines that save their input, thereby insuring a global 1: 1 relation between initial and final IDs, even when the function being computed is many-to-one. Reversible machines that instead erase their input can of course compute only 1: 1 partial recursive functions and indeed provide a Godel numbering of such functions. The time/space cost of computing a 1: 1 function on such a machine is equal within a small polynomial to the cost of computing the function and its inverse on an ordinary Turing machine.