>Abstract. The theory of reversible computing is based on invertible 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 it
is ideally possible to build sequential circuits with zero internal power dissipation.
>In 1970s, Ed Fredkin, Tommaso Toffoli, and others at MIT formed the Information Mechanics group to the study the physics of information. As we will
see, Fredkin and Toffoli described computation with idealized, perfectly elastic balls reflecting o↵ barriers. The balls have minimum dissipation and are
propelled by (conserved) momentum. The model is unrealistic but illustrates
many ideas of reversible computing. Later we will look at it briefly (Sec. C.7).
>They also suggested a more realistic implementation involving “charge packets bouncing around along inductive paths between capacitors.” Richard
Feynman (Caltech) had been interacting with Information Mechanics group,
and developed “a full quantum model of a serial reversible computer” (Feynman, 1986).
>Charles Bennett (1973) (IBM) first showed how any computation could be
embedded in an equivalent reversible computation. Rather than discarding
information (and hence dissipating energy), it keeps it around so it can later
“decompute” it back to its initial state. This was a theoretical proof based on
Turing machines, and did not address the issue of physical implementation. [...]
>How universal is the Toffoli gate for classical reversible computing:
