COMPUTING SCIENCE

# Reverse Engineering

backward and forward both run to need may they ,faster run to are computers If

Reversible Logic

A Turing machine is fine for reasoning about computers, but it's not an ideal model for building them. Some more practical components of reversible logic were introduced in the 1980s by Edward F. Fredkin and Tommaso Toffoli, who were then working together at MIT. (Fredkin is now at Carnegie Mellon University, Toffoli at Boston University.) The components are logic gates, somewhat like AND and OR gates but designed for reversibility.

In any reversible gate the number of inputs must equal the number of outputs. Moreover, each possible set of inputs must yield a distinct set of outputs. If this were not the case—that is, if two or more input patterns had the same output—then the reverse action of the gate would be ambiguous.

The devices now known as the Fredkin gate and the Toffoli gate
*(see illustration on page 109)* both have three inputs
and three outputs; and, as required for reversibility, each input
pattern maps to a unique output. In the Fredkin gate, one signal
controls whether the other two data lines pass straight through the
gate or else have their positions swapped. In the Toffoli gate, two
of the signals control the third; if the first two bits are both 1,
then the third bit is inverted.

Like the NOT gate, both the Fredkin and the Toffoli gates are their own inverses: No matter what the values of the three input signals, running them through two successive copies of the same gate will return the signals to their original values. Both gates are also computationally universal, meaning that a computer assembled from multiple Fredkin or Toffoli gates (and no other components) could simulate a Turing machine or any other device of equivalent computational power. Thus the gates might be considered candidates for a real reversible computer.

Of course logic gates are still just abstract devices; they have to be given some physical implementation with transistors or other kinds of hardware. Starting in the early 1990s, several groups have been designing and building prototypes of reversible (or nearly reversible) digital circuits. For example, at MIT a group including Michael Frank and Thomas F. Knight, Jr., fabricated a series of small but complete processor chips based on a reversible technology; Frank continues this work at Florida State University. At the University of Gent in Belgium, Alexis De Vos and his colleagues have built several reversible adders and other circuits.

It's important to note that building a computer according to a
reversible logic diagram does not guarantee low-power operation.
Reversibility removes the thermodynamic floor at *kT ln* 2,
but the circuit must still be designed to attain that level of
energy savings. The current state of the art is far above the
theoretical floor; even the most efficient chips, reversible or not,
dissipate somewhere between 10,000 and 10 million times *kT*
ln 2 for each logical operation. Thus it will be some years before
reversible technology can be put to the ultimate test of challenging
the three-zeptojoule barrier. In the meantime, however, it turns out
that some concepts derived from reversible logic are already useful
in low-power circuits. One of these is charge recovery, which
attempts to recycle packets of electric charge rather than let them
drain to ground. Another is adiabatic switching, which avoids
wasteful current surges by closing switches only after voltages have
had a chance to equalize.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Engineering**: Traffic Signals, Dilemma Zones, and Red-Light Cameras

**Computing Science**: Computer Vision and Computer Hallucinations

**Spotlight**: Making the Cut