Efficient turing-universal computation with DNA polymers
Bennett’s proposed chemical Turing machine is one of the most important thought experiments in the study of the thermodynam- ics of computation. Yet the sophistication of molecular engineering re- quired to physically construct Bennett’s hypothetical polymer substrate and enzymes has deterred experimental implementations. Here we pro- pose a chemical implementation of stack machines — a Turing-universal model of computation similar to Turing machines — using DNA strand displacement cascades as the underlying chemical primitive.More specif- ically, the mechanism described herein is the addition and removal of monomers from the end of a DNA polymer, controlled by strand displace- ment 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.