Time/Space Trade-Offs for Reversible Computation

TLDR

Reversible Turing machines have a bijective transition function, ensuring each instantaneous description has a unique predecessor, and by preserving input they maintain a global one‑to‑one mapping between initial and final configurations even for many‑to‑one functions. Using a pebbling argument, the authors prove that any ordinary multitape Turing machine running in time T and space S can be simulated by a reversible machine in time O(T^{1+ε}) and space O(S log T) (or linear time and space O(ST^ε)), implying reversible machines can emulate ordinary ones with at most quadratic space; reversible machines that erase input compute only 1:1 partial recursive functions, and their time/space cost is polynomially equivalent to that on ordinary machines.

Abstract

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 $\varepsilon > 0$, ordinary multitape Turing machines using time T and space S can be simulated by reversible ones using time $O(T^{1 + \varepsilon } )$ and space $O(S\log T)$ or in linear time and space $O(ST^\varepsilon )$. 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.