Title :
Reversible simulation of irreversible computation
Author :
Li, Ming ; Vitanyi, Paul
Author_Institution :
Dept. of Comput. Sci., Waterloo Univ., Ont., Canada
Abstract :
Reversible simulation of irreversible algorithms is analysed 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 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. We give a trade-off of storage space versus irreversible erasure. Examples of reversible algorithms are algorithms for quantum computers
Keywords :
algorithm theory; computational complexity; game theory; Bennett´s simulation; computation time; irreversible computation; irreversible erasure; memory space; pebble game; reversible algorithms; reversible simulation; Analytical models; Computational modeling; Computer science; Cooling; Energy dissipation; Physics computing; Quantum computing; Switches; Temperature; Thermodynamics;
Conference_Titel :
Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
Conference_Location :
Philadelphia, PA
Print_ISBN :
0-8186-7386-9
DOI :
10.1109/CCC.1996.507692