COMPUTING SCIENCE
Reverse Engineering
backward and forward both run to need may they ,faster run to are computers If
Brian Hayes
Most of the machines we encounter in everyday life are one-way
devices. Kitchen appliances turn bread into toast and cabbage into
cole slaw, but they cannot perform the opposite transformations.
Even machines that claim to be reversible adopt a very shallow
notion of what it means to go backwards. The drill in my tool box
has settings marked "forward" and "reverse," but
no matter which I choose, I cannot undrill a hole. The gearshift in
my car also has a position labeled R, but when I back up,
the engine keeps turning in the same direction; if the car were
truly reversed, it would suck in pollution through the
tailpipe, converting it into gasoline and air.
Computers, too, are mostly irreversible machines. When a program is
running, there's no way to turn it around and have it step through
the same instructions in the opposite order. Even if that were
feasible, the backward-running program would not uncompute an
answer. Some of the individual instructions would also have to be
reversed, or inverted; for example, undoing addition requires
subtraction. For computers of the current generation, such reversals
of logic and arithmetic are simply not possible.
In the case of toasters and gasoline engines, full reversibility is
too much to ask, but no fundamental law forbids reversible
computing. The theoretical possibility of a digital computer that
can run forward and backward with equal ease has been recognized for
more than 30 years. A few silicon prototypes have been built and
shown to work. Still, up to now, reversible computing has been a toy
technology, more of interest to theorists than to engineers. Only a
small community of devotees believed it would ever be anything more.
That attitude is changing now. The reason is that reversible
computing holds out the promise of dramatically lower power
consumption, which is becoming an urgent need. Also, any computer
based on quantum technology will necessarily be a reversible
machine. As a result, forward-thinking chip designers are thinking
backwards too. It's not too soon to ask what it might be like to
have a reversible computer on your desk, or to write programs that
can run in either direction.
» Post Comment