COMPUTING SCIENCE
Reverse Engineering
backward and forward both run to need may they ,faster run to are computers If
Brian Hayes
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.
» Post Comment