REVERSIBLE COMPUTING
Tommaso Toffoli
MIT Laboratory for Computer Science
545 Technology Sq., Cambridge, MA 02139
Abstract. The theory of reversible computing is based on invertib|e primitives
and composition rules that preserve invertibility. With these constraints, one can still
satisfactorily deal with both functional and structural aspects of computing processes;
at the same time, one attains a closer correspondence between the behavior of abstract
computing systems and the microscopic physical laws (which are presumed to be
strictly reversible) that underly any concrete implementation of such systems.
According to a physical interpretation, the central result of this paper is that i¢
is ideally possible to build sequential c/rcuits with zero internal power dissipation.
L Introduction
This is an abridged version of a much longer report of the same title[27], to which
the reader may turn for further details, most proofs, and extended references. Here, the
numbering of formulas, figures, etc. reflects that of the original version.
Mathematical models of computation are abstract constructions, by their nature un-
fettered by physical laws. However, if these models are to give indications that are relevant
to concrete computing, they must somehow capture, albeit in a selective and stylized
way, certain general physical restrictions to which all concrete computing processes are
subjected.
O n e of the strongest motivations for the study of reversible computing comes from
the desire to reduce heat dissipation in computing machinery, and thus achieve higher
density and speed. Briefly, while the microscopic laws of physics are presumed to be
strictly reversible, abstract computing is usually thought of as an irreversible process,
since it m a y involve the evaluation of many-to-one functions. Thus, as one proceeds d o w n
from an abstract computing task to a formal realizationby means of a digital network and
finally to an implementation in a physical system, at some level of this modeling hierarchy
there must take place the transition from the irreversibilityof the given computing process
to the reversibility of the physical laws. In th.ccustomary approach, this transition occurs
at a very low level and is hidden--so to speak--in the "physics" of the individual digital
gate;* as a consequence of this approach, the detailsof the work-to-heat conversion process
are put beyond the reach of the conceptual model of computation that is used.
O n the other hand, it is possible to formulate a more general conceptual model of
computation such that the gap between the irreversibilityof the desired behavior and the
reversibility of a given underlying mechanism is bridged in an explici~ way within the
model itself. This we shall do in the present paper.
~'~ypically, the computation is logically organized around computing primitives that are
not invertible, such as the N^NDgate; in turn, these are realized by physical devices which,
while by their nature obeying reversible microscopic laws, are made macroscopically irre-
versible by allowing them to convert some work to heat.
633
An important advantage of our approach is that any operations (such as the clearing
of a register) that in conventional logic lead to the destruction of macroscopic informa-
tion, and thus entail energy dissipation, here can be planned at the whole-circuit level
rather than at the gate level, and most of the time can be replaced by an information-
losstess variant. As a consequence, it appears possible to design circuits whose internal
power dissipation, under ideal physical circumstances, is zero. The power dissipation t h a t
would arise at the interface between such circuits and the outside world would be at most
proportional to the number of input/output lines, rather than to the number of logic gates.
2. Terminology and notation
A function 4: X - ~ Y is finite if X and Y are finite sets. A finite automaton is a
dynamical system characterized by a transition function of the form r : X X Q --~ Q X Y,
where r is finite. Without loss of generality, one may assume that such sets as X, Y, and
Q above be explicitly given as indexed Cartesian products of sets. We shall occasionally
call lines the individual variables associated with the individual factors of such products.
In what follows, we shall assume once and for all that all factors of the aforementioned
Cartesian products be identical copies of the Boolean set B ---~ (0,1). A finite function is
of order n if it has n input lines.
The process of generating multiple copies of a given signal must be treated with
particular care when reversibility is an' issue (moreover, from a physical viewpoint this
process is far from trivial). For this reason, in all that follows we shall restrict the meaning
of the term "function composition" to one-to-one composition, where any substitution of
o u t p u t variables for input variables is one-to-one. Thus, any "fan-out" node in a given
function-composition scheme will have to be treated as an explicit occurrence of a fan-
o u t function of the form (x) H (x,..., x). Intuitively, the responsibility for providing fan-
o u t is shifted from the composition rules to the computing primitives.
Abstract computers (such as finite automata and Turing machines) are essentially
function-composition schemes. It is customary to expJ'ess a function-composition scheme
in graphical form as a causality network. This is basically an acyclic directed graph in
which nodes correspond to functions and arcs to variables. By construction, causality
networks are "loop-free," i.e., they contain no cyclic paths. A combinational network is
a causality network that contains no infinite paths. Note that a finite causality network
is always a combinational one. With certain additional conventions (such as the use of
special markers called delay elements), causality networks having a particular iterative
structure can be represented more compactly as sequential networks.
A causality network is reversible if it is obtained by composition of invertible primi-
tives. Note that a reversible combinational network a|ways defines an invertible function.
Thus, in the case of combinational networks the structural aspect of "reversibility" and
the functional aspect of "invertibility" coincide. A sequential network is reversible if
its combinational part (i.e., the combinational network obtained by deleting the delay
elements and thus breaking the corresponding arcs) is reversible.
We shall assume familiarity with the concept of "realization" of finite functions and
a u t o m a t a by means of, respectively, combinational and sequential networks. In w h a t
follows, a "realization" will always mean a componentwise one; that is, to each input (or
output) line of a finite function there will correspond an input (or output) line in the
combinational network that realizes it, and similarly for the realization of a u t o m a t a b y
sequential networks.
