A Reversible NAND Gate

The great discovery of Bennett and, independently, of Fredkin is that it is possible to do computation with a different kind of fundamental gate unit, namely, a reversible gate unit. I have illustrated their idea--with a unit which I could call a reversible NAND gate. It has thre inputs and thre outputs. Of the outputs, tow, A' and B', are the same as two of the inputs, A and B, but the third input works this way. C' is the same as C unless A and B are both 1, in which case it changes whatever C is. For instance, if C is 1 it is changed to 0, if C is 0 it is changed to 1--but these changes only happen if both A and B are 1. If you put two of these gates in succession, you see that A and B will go through, and if C is not changed in both it stays the same. If C is changed, it is changed twice so that it stays the same. So this gate can reverse itself and no information has been lost. It is possible to discover what wnet in if you know what came out.

Feynman describes a reversible logic gate, with three inputs and three outputs, one of which tracks the change in input and output, allowing the computer to reverse its operation and potentially pursue a different route.