InterJournal Complex Systems, 53
Status: Accepted
Manuscript Number: [53]
Submission Date: 963011
Space-energy trade-off in reversible simulations
Author(s): Ming Li ,Paul Vitanyi

Subject(s): CX.07

Category: Brief Article


Reversible simulation of irreversible algorithms is analyzed in the stylized form of a `reversible pebble game. While such simulations incur little overhead in additional computation time, they use a large amount of additional memory space during the computation. We show that among all simulations which can be modeled by the pebble game, Bennetts simulation is optimal in that it uses the least auxiliary space for the greatest number of simulated steps. We give a trade-off of storage space versus irreversible erasure.

Retrieve Manuscript
Submit referee report/comment

Public Comments: