Physics – Quantum Physics
Scientific paper
1997-03-06
Physica D120 (1998) 168-176
Physics
Quantum Physics
11 pages, Latex, Submitted to Physica D
Scientific paper
10.1016/S0167-2789(98)00052-9
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. The reacheable reversible simulation instantaneous descriptions (pebble configurations) are characterized completely. As a corollary we obtain the reversible simulation by Bennett and that among all simulations that can be modelled by the pebble game, Bennett's simulation is optimal in that it uses the least auxiliary space for the greatest number of simulated steps. One can reduce the auxiliary storage overhead incurred by the reversible simulation at the cost of allowing limited erasing leading to an irreversibility-space tradeoff. We show that in this resource-bounded setting the limited erasing needs to be performed at precise instants during the simulation. We show that the reversible simulation can be modified so that it is applicable also when the simulated computation time is unknown.
Li Ming
Tromp John
Vitanyi Paul
No associations
LandOfFree
Reversible Simulation of Irreversible Computation by Pebble Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Reversible Simulation of Irreversible Computation by Pebble Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reversible Simulation of Irreversible Computation by Pebble Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-451719