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

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).