Erik Winfree (California Institute of Technology)
Abstract. "Bennett’s proposed chemical Turing machine is one of the most important thought experiments in the study of the thermodynamics of computation. Yet the sophistication of molecular engineering required to physically construct Bennett’s hypothetical polymer substrate and enzyme has deterred experimental implementations. Here we propose a chemical implementation of stack machines — a Turing-universal model of computation similar to Turing machines — using strand displacement cascades as the underlying chemical primitive. More specifically, the mechanism described herein is the addition and removal of monomers from the end of a polymer, controlled by strand displacement logic. We capture the motivating feature of Bennett’s scheme — that physical reversibility corresponds to logically reversible computation, and arbitrarily little energy per computation step is required. Further, as a method of embedding logic control into chemical and biological systems, polymer-based chemical computation is significantly more efficient than geometry-free chemical reaction networks."
Bio. Erik Winfree is Professor of Computer Science, Computation & Neural Systems and Bioengineering at Caltech. He is the recipient of the Feynman Prize for Nanotechnology (2006), the Tulip prize in DNA Computing (2003), the NSF PECASE/CAREER Award (2001), the ONR Young Investigators Award (2001), a MacArthur Fellowship (2000), and MIT Technology Review's first TR100 list of "top young innovators" (1999). Prior to joining the faculty at Caltech in 1999, Winfree was a Lewis Thomas Postdoctoral Fellow in Molecular Biology at Princeton, and a Visiting Scientist at the MIT AI Lab. Winfree received a B.S. in Mathematics and Computer Science from the University of Chicago in 1991, and a Ph.D. in Computation & Neural Systems from Caltech in 1998.