Joint Penn-UDel Colloquium on the Nature of Computing

Reversible Computation Using DNA: Through
The Fredkin Gate On A Watson-Crick Wagon

Harvey Rubin
Medical School, University of Pennsylvania

Truth table for a Fredkin Gate.

INPUT OUTPUT CONTROL A B CONTROL A B 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0

A Fredkin gate is a reversible logic element, from which no information is discarded, containing three input channels and three output channels. One of the input channels serves as a control line that remains unchanged by the gate but determines the output of the other two input channels. If the control line is set at 1 the output of the other two lines interchanges. If the control channel is set at 0 the other two lines go through the gate unchanged. An assembly of Fredkin gates is capable of universal computation. We show how to realize a Fredkin gate using the enzymatic reactions associated with DNA amplification and demonstrate experimentally the correspondence between computation and biochemistry in a real system.

1. Fredkin, E. and Toffoli, T. Conservative Logic. International Journal of Theoretical Physics 21, 219, 1982.
2. Bennett C.H. and Landauer, R. The Fundamental Physical Limits of Computation. Scientific American July 1985 v 253 p48.
3. Feynman, R.P. Feynman Lectures on Computation; edited by Anthony J.G. Hey and Robin W. Allen. Addison-Wesley, Reading, MA, 1996.