Lambda the Ultimate

inactiveTopic A structural approach to reversible computation
started 4/30/2003; 6:44:02 AM - last post 5/2/2003; 3:49:24 PM
Ehud Lamm - A structural approach to reversible computation  blueArrow
4/30/2003; 6:44:02 AM (reads: 1816, responses: 3)
A structural approach to reversible computation
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

Ehud Lamm - Re: A structural approach to reversible computation  blueArrow
4/30/2003; 12:20:16 PM (reads: 724, responses: 0)
Several useful papers on reversible computation can be found here.

Ken Shan - Re: A structural approach to reversible computation  blueArrow
5/2/2003; 12:31:03 PM (reads: 626, responses: 0)
How can I acquire enough background knowledge to understand this article? A list of recommended readings would be greatly appreciated.

Vlad S. - Re: A structural approach to reversible computation  blueArrow
5/2/2003; 3:49:24 PM (reads: 616, responses: 0)
Today I was looking for some paper Henry Baker wrote, and I came across two unrelated ones on the subject of reversible garbage collection here and here (I only skimmed them, but both seem to have lots of introductory information on reversible computation; the whole subject is a little thick for me and I'm too busy to read through all this good stuff right now).