What's Reversible Computing?

When we say reversible computing, we mean performing computation in such a way that any previous state of the computation can always be reconstructed given a description of the current state. Such a computation is "reversible" since the reconstruction of previous states could be applied to allow progressing backwards through the computer's sequence of states, in a time-reversed fashion. Maintaining the property of reversibility requires that no information about the state of the computer can ever be thrown away.

This might seem to be a severe restriction, causing a reversible computer's memory to fill up quickly with all the intermediate results that are normally thrown away during a computation. However, it turns out that reversibility can actually be maintained with only a very gradual increase in storage requirements, given some modest overhead in terms of computation time. Moreover, it seems that many interesting tasks can be performed reversibly without any significant memory or time overhead. Also, reversibility isn't an all-or-nothing proposition; if the overhead of total reversibility is too high, it can be greatly reduced by allowing information to be thrown away occasionally, while still allowing almost all of the benefits of the reversibility to be realized.

Reversible computing may have applications in computer security and transaction processing, but we anticipate that the main long-term benefit will be to allow faster, smaller computers. You see, physics itself is actually reversible, and so whenever a computer is supposedly "erasing" some piece of information (e.g. by grounding a circuit node that is holding charge representing a bit of information), in actuality that information is only being changed into a different form, namely heat, and the removal of this heat puts severe limits on the amount of computation that can be performed in a small, compact volume of space in a short time.1

If, on the other hand, the computer's operation is reversible, then any unwanted information can be managed in a much more efficient fashion, and can often be reabsorbed back into the state of the computation, never requiring dissipation to heat, or removal from the system. We believe this trick of avoiding information removal will ultimately allow much higher computational density to be achieved than if computers remain irreversible and continuously produce unwanted information which must be removed by cooling mechanisms which are relatively inefficient.

Up to Mike's Reversible Computing Page.


Michael Frank
Last modified: Tue Nov 5 01:09:56 EST