MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > May-June 2006 > Article Detail

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.