merkle.pa@xerox.com (07/01/89)
JoSH wrote: [I am not convinced that a useful computer can be built of Fredkin or other reversible logic. The reason is that the "trick" depends on not destroying information. Maxwell's demon uses energy (entropy really, but it takes "useful work" ie energy, to destroy entropy) not in finding a molecule, but in forgetting it to get ready for the next one. Let me put it another way: to build a Fredkin gate machine, you must connect *all* of the outputs to something--no dangling wires. To make something useful you wind up in effect continuously writing the state of the machine out into memory. And you can't clear the memory to start over, or you use up all the energy you saved by using Fredkin gates in the first place. --JoSH] This issue is discussed in some detail in "Conservative Logic" by Edward Fredkin and Tommaso Toffoli, Internation Journal of Theoretical Physics, Vol. 21, Nos. 3/4, 1982. Basically, you run the computation forwards until you get the desired answer, then (because the logic gates are all reversible) you run the computation backwards (eating up the "waste" outputs as you go) until you reach the initial condition. Result? You get exactly the output that you want, and no "waste output" is left. They also discuss a more ingenious scheme for use with "any invertible, conservative function." If we design an "invertible" cpu from an "invertible" instruction set, it can in principle compute with negligible energy dissipation. To quote their paper: "With some ingenuity, it is possible to design in this fashion general-purpose conservative logic computers (Ressler, 1981) based on the Fredkin gate, having a circuit complexity comparable, in terms of number of gates, with that of ordinary computers based on the NAND gate." (The reference is to: A. Ressler, "The design of a conservative logic computer and a graphical editor simulator", MS thesis, MIT, EECS Dept. (Jan. 1981)
peb@tma1.sun.com (Paul Baclaski) (07/13/89)
In article <Jun.30.22.28.23.1989.15406@athos.rutgers.edu>, merkle.pa@xerox.com writes: > This issue is discussed in some detail in "Conservative Logic" by Edward > Fredkin and Tommaso Toffoli, Internation Journal of Theoretical Physics, > Vol. 21, Nos. 3/4, 1982. > > Basically, you run the computation forwards until you get the desired > answer, then (because the logic gates are all reversible) you run the > computation backwards (eating up the "waste" outputs as you go) until you > reach the initial condition. Result? You get exactly the output that you > want, and no "waste output" is left. They also discuss a more ingenious Is there a cost for reversal (I would guess that the machine would have a register for "direction of time".. )? Obviously, this would slow down throughput by a factor of 2. There must be a cost for reprogramming the machine or if it does any i/o. Thus, the cost may be very low, but it is not zero. Paul E. Baclaski Sun Microsystems peb@sun.com