Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!aramis.rutgers.edu!athos.rutgers.edu!nanotech From: merkle.pa@xerox.com Newsgroups: sci.nanotech Subject: Reversible logic -- is it practical? Message-ID: Date: 1 Jul 89 02:28:25 GMT Sender: nanotech@athos.rutgers.edu Lines: 34 Approved: nanotech@aramis.rutgers.edu 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)