COMPUTING SCIENCE

# Reverse Engineering

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

Back to the Future

Making a computer run backwards is not just a problem for hardware hackers and logic designers. There are also issues at higher levels of abstraction. What will it be like to write and run a program on a machine that can bounce back and forth in time?

Most of us already have some experience with a rudimentary form of
reversibility—namely the *undo* command. Even this
simple facility for unwinding a computation has its semantic
hazards. (Should "*undo undo*" leave you two steps
back, or none?) In many programs, *undo* is a bit of a sham;
it doesn't turn the program around but just revisits saved
snapshots. Software that *really* runs in reverse has some
harder problems to solve.

Consider the matter of rounding. Most numerical calculations are done with limited precision; all numbers have to fit into 32 bits, say. When that's not enough room, the least-significant digits are discarded. But dropping digits is a no-no in the world of reversible computing. If 1/3 gets converted into 0.33333, then reversing the process must somehow yield exactly 1/3 again.

Even arithmetic with exact numbers can get us into trouble, if one of those numbers happens to be zero. Division by zero is forbidden everywhere in civil society; in a reversible machine, we might also have to outlaw multiplication by zero, because it amounts to erasure, yielding a result of zero no matter what the value of the multiplicand. Personally, I rather like this idea of treating division and multiplication symmetrically, but it runs counter to hundreds of years of habit.

Henry G. Baker, in a thoughtful essay that touches on several issues
of reversibility, cites another example: Newton's method for
approximating square roots. In Newton's algorithm, you approach the
square root of *N* by starting with an arbitrary guess,
*x*, and then calculating (x + N/x)/2. The result of this
expression becomes a new guess, and you repeat the procedure until
you reach the desired accuracy. Almost any guess will converge on
the true root; in other words, the algorithm "exemplifies a
large class of computations in which the output appears to be
independent of the input." The method also appears to be highly
irreversible, since all those different inputs lead to the same
output. If the computation were reversed, how could the algorithm
find its way back from the one output to each of the many possible
inputs? But in fact it can (at least if the initial *x* is
greater than the square root of *N*). If the computation is
done without rounding or truncating intermediate results, all of the
information needed to reverse the process is preserved in the
"insignificant" decimal places of the answers. Each
initial guess can be reconstructed exactly.

Baker and others also point out that a reversible computer would be a wonderful device for debugging programs. With conventional hardware, you can set a breakpoint to stop a program when it goes off the rails, but then it's a struggle to figure out what path brought it to the trouble spot. With a reversible device, you can just back it up. Running a compiler in reverse might also be fun. Generating source code from an executable program is a handy trick (which the vendors of commercial software would no doubt want to disable).

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