Reversible computing

Reversible computing, sometimes called non-destructive computing[1] includes any computational process that is (at least to some close approximation) reversible; i.e., time-invertible, meaning that a time-reversed version of the process could exist within the same general dynamical framework as the original process. For example, within the context of deterministic dynamical frameworks, a necessary condition for reversibility is that the transition function mapping states to their successors at a given later time should be one-to-one.

Probably the largest motivation for the study of hardware and software technologies aimed at actually implementing reversible computing is that they offer what is predicted to be the only potential way to improve the energy efficiency of computers beyond the fundamental von Neumann-Landauer limit [2] of kT \cdot \ln2\! energy dissipated per irreversible bit operation, where k is Boltzmann's constant of 1.38 × 10−23 J/K, and T is the temperature of the environment into which unwanted entropy will be expelled.

There are two major, closely-related, types of reversibility that are of particular interest for this purpose: physical reversibility and logical reversibility. A process is said to be physically reversible if it results in no increase in physical entropy; it is isentropic. Although in practice no nonstationary physical process can be exactly physically reversible or isentropic, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well-isolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known.

As was first argued by Rolf Landauer of IBM,[3] in order for a computational process to be physically reversible, it must also be logically reversible. Landauer's principle is the loosely formulated notion that the erasure of n bits of information must always incur a cost of nk \cdot \ln2\! in thermodynamic entropy. A discrete, deterministic computational process is said to be logically reversible if the transition function that maps old computational states to new ones is a one-to-one function; i.e. the output logical states uniquely defines the input logical states of the computational operation.

For computational processes that are nondeterministic (in the sense of being probabilistic or random), the relation between old and new states is not a single-valued function, and the requirement needed to obtain physical reversibility becomes a slightly weaker condition, namely that the size of a given ensemble of possible initial computational states does not decrease, on average, as the computation proceeds forwards.