MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > March-April 2006 > Article Detail

COMPUTING SCIENCE

# Reverse Engineering

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

An Unturing Machine

Although erasing takes energy, Landauer found that not all computer operations are subject to the three-zeptojoule stricture. The simplest counterexample is the logical NOT gate, which inverts the state of a single bit, changing 1 to 0 or 0 to 1. No information is lost in this process; the state of the bit is completely known both before and after. Thus there is no fundamental reason for a NOT gate to be dissipating energy. Present-day implementations of the NOT function may very well produce just as much heat as erasing a memory cell, but that energy loss is not required by the laws of thermodynamics.

A notable property of the NOT function is its reversibility. When bit A is transformed into NOT A, all that's needed to undo the action and restore the original state is a second application of the NOT function—(NOT (NOT A)) = A. The erasure of a bit is quite different; it can't be undone because there's no way of knowing whether the previous state was a 0 or a 1.

Functions such as AND are also logically irreversible. A two-input AND gate produces an output of 1 if and only if both inputs are 1; otherwise the output is 0. Thus if the output happens to be 1, we know that both inputs were also 1, but when the output is 0, we can't distinguish between three alternative pairs of inputs (0 and 1, 1 and 0, 0 and 0). A similar analysis applies to OR. At a higher level, standard arithmetic operations such as +, -, x and ÷ also throw away information and are therefore irreversible. Take the equation 5 + 3 = 8; given the left side, it's easy to regenerate the right, but you can't go the other way.

Landauer showed that only the logically irreversible steps in a computation carry an unavoidable energy penalty. If we could compute entirely with reversible operations, there would be no lower limit on energy consumption. We could run a supercomputer on a watch battery.

The question remained: Is it possible to build a fully capable computer out of nothing but logically reversible components? Initially, Landauer himself thought the answer was no. After all, most of the familiar building blocks of computers, such as AND and OR gates, are irreversible devices. Then in 1973 Charles H. Bennett, now of IBM Research, came up with a remarkably direct demonstration that any computation by an irreversible computer can also be done reversibly.

Bennett presented his idea in terms of a Turing machine, the abstract model of a computer that reads, writes and erases symbols on a tape. Erasures make the standard Turing machine irreversible, so Bennett added a second tape, called the history tape, where the machine keeps notes about erased or overwritten data. At the end of a computation, the final answer can be copied onto yet another tape for safekeeping. Then the machine is put in reverse gear, and with the help of the history tape, all the operations are undone, one by one, until the system returns to its initial condition.

The latter half of this operating cycle strikes many people as bizarrely counterproductive. How can you save energy by running the machine for twice as long, regardless of whether it's going forward or backward? Wouldn't it be better just to throw away the extra tape? Experience with ordinary machines in everyday life does not prepare us to answer these questions. When you drive a car 10 miles down the road, you can't recover the fuel you burned by backing up over the same route. But suppose the car had a history tape that kept track of all the molecules involved in the combustion process; then, in principle, you could unburn the gasoline by bringing those molecules back together in the right order. This is not a feasible scheme in automotive engineering, but in the tidier, discrete universe of digital computers, the history-tape trick does work.

Maybe even the reverse-combustion process isn't quite as outlandish as it seems. Bennett, who began his career as a chemist, also described a biochemical model of a reversible computation. When the enzyme RNA polymerase reads off the sequence of bases in a strand of DNA and assembles a corresponding molecule of RNA, the RNA is conceptually equivalent to the history tape in Bennett's Turing machine. The same enzyme can then work in reverse to disassemble the RNA, base by base—but only for RNA that matches the DNA template. Bennett points out that this orderly reversal of the assembly process is energetically more efficient than disposing of the RNA with enzymes that degrade any such molecule.

EMAIL TO A FRIEND :

Of Possible Interest

Computing Science: Computer Vision and Computer Hallucinations

Spotlight: Making the Cut