Lulu Qian


previous Stack machines made of DNA polymers next

We propose 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 specifically, the mechanism described herein is the addition and removal of monomers from the end of a DNA polymer, controlled by strand displacement logic. We capture the physical reversibility that 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.

[1] Efficient Turing-universal computation with DNA polymers. Lulu Qian, David Soloveichik, and Erik Winfree. Lecture Notes in Computer Science, 6518:123-140, 2011. (pdf)