|
We present a simple model of computation which is directly reversible in a very strong sense - every automaton A in our model has a "dual" automaton Aop, defined quite trivially from A, whose computations are exactly the time-reversals of the computations of A. We then establish a connection to models of functional computation. We will show that our model gives rise to a combinatory algebra, and derive universality as an easy consequence. This method of establishing universality has potential significance for the important issue of how to program reversible computations. Our approach can be seen as providing a simple, compositional (i.e. "syntax-directed") compilation from high-level functional programs into a reversible model of computation.
Reversible computing is a highly intereseting and important notion: It can be shown that there exists a minimal amount of heat (energy) that must be dissipated for any irreversible bit change. Quite surprisingly, compuations that can be reversed in time are exempt from this constraint. Essentially, this means that we can reduce the heat produced, and increase energy efficiency.
This paper shows one approach for compiling functional programs for a reversible computation model.
The paper proceeds as follows: First the model is defined (this part is a bit hard to follow), than the connection to combinatory logic is explained (the paper briefly explains what combinatory logic is, but see the Lambda Birds for more information). Finally, the method of compiling functional programs into reversible computations is explained and analyzed.
Posted to general by Ehud Lamm on 4/30/03; 6:51:38 AM
|
|
A structural approach to reversible computation
