[34] Let an irreversible computation use t steps and s space. (a) Show how to simulate it reversibly using t = (t1+/s) steps and s

[34] Let an irreversible computation use t steps and s space.

(a) Show how to simulate it reversibly using t = Θ(t1+/s) steps and s = Θ(c()s(1 + log t/s)) space with c() = 21/ for any  > 0 using always the same simulation method with different parameters. Typically,

 = log 3.

(b) Show that Item

(a) implies that each irreversible computation using s space can be simulated by a reversible computation using s2 space in t

 = Θ(t 1+) time.

Comments. Hint: In Item

(a) do not save the entire history of the irreversible computation, but break up the simulated computation into segments of about s steps and save in a hierarchical manner checkpoints consisting of complete instantaneous descriptions of the simulated machine (entire tape contents, tape heads positions, state of the finite control). After a later checkpoint is reached and saved, the simulating machine reversibly undoes its intermediate computation reversibly erasing the intermediate history and reversibly canceling the previously saved checkpoint. Subsequently, the computation is resumed from the new checkpoint onward. The reversible computation simulates kn segments of length m of irreversible computation in (2k − 1)n segments of length Θ(m+s) of reversible computation using n(k −1) + 1 checkpoint registers using Θ(m+S) space each, for each k, n, m. In this way, it is established that there are various tradeoffs possible in time–space between t = Θ(t) and s = Θ(ts) at one extreme (k = 1, m = t, n = 1) and the t

and s in Item

(a) at the other extreme using always the same simulation method but with different parameters k, n, where  = logk(2k − 1) and m = Θ(s). Typically, for k = 2 we have  = log 3. Since for t > 2s the machine goes into a computational loop, we always have s ≤ log t. This proves Item (b). Source: for Items

(a) and

(b) [C.H. Bennett, SIAM J.

Comput., 18(1989), 766–776; R.Y. Levine and A.T. Sherman, SIAM J.

Comput., 19(1990), 673–677]. In [M. Li and P.M.B. Vit´anyi, Proc. Royal Soc. London, Ser. A, 452(1996), 769–789], reversible simulations are investigated using reversible pebble games. It is shown that the simulations as in Item

(a) are optimal in the sense of simulating the greatest number of steps using least space overhead s − s. It is shown that the space overhead can be reduced at the cost of limited irreversible erasing. By Landauer’s principle this implies a space–energy tradeoff. For further results on time–space bounds for reversible simulation of irreversible computation, see [M. Li, J.T. Tromp, and P.M.B. Vit´anyi, Physica D, 120(1998) 168–176; K.J. Lange, P. McKenzie, and A. Tapp, J. Comput.

Syst. Sci., 60:2(2000), 354–367; H.M. Buhrman, J.T. Tromp, and P.M.B.
Vit´anyi , J. Physics A: Math. and General, 34(2001), 6821–6830].