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 enzymes has deterred experimental implementations. Here 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 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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adleman, L.: Molecular Computation of Solutions to Combinatorial Problems. Science 266(5187), 1021–1024 (1994)
Beaver, D.: A Universal Molecular Computer. In: Lipton, R., Baum, E. (eds.) DNA Based Computers, pp. 29–36. AMS, Providence (1996)
Benenson, Y., Paz-Elizur, T., Adar, R., Keinan, E., Livneh, Z., Shapiro, E.: Programmable and autonomous computing machine made of biomolecules. Nature 414(6862), 430–434 (2001)
Benenson, Y., Shapiro, E.: Molecular computing machines. In: Encyclopedia of Nanoscience and Nanotechnology, pp. 2043–2056 (2004)
Bennett, C.: Logical reversibility of computation. IBM Journal of Research and Development 17(6), 525–532 (1973)
Bennett, C.: The thermodynamics of computation – a review. International Journal of Theoretical Physics 21(12), 905–940 (1982)
Bennett, C.: Time/space trade-offs for reversible computation. SIAM Journal on Computing 18, 766–776 (1989)
Blinov, M., Faeder, J., Goldstein, B., Hlavacek, W.: BioNetGen: software for rule-based modeling of signal transduction based on the interactions of molecular domains. Bioinformatics 20(17), 3289–3291 (2004)
Cardelli, L.: Strand algebras for DNA computing. In: Deaton, R., Suyama, A. (eds.) DNA 15. LNCS, vol. 5877, pp. 12–24. Springer, Heidelberg (2009)
Cardelli, L.: Two-Domain DNA Strand Displacement. In: Developments in Computational Models (DCM), pp. 33–47 (2010)
Cardelli, L., Zavattaro, G.: On the computational power of biochemistry. In: Horimoto, K., Regensburger, G., Rosenkranz, M., Yoshida, H. (eds.) AB 2008. LNCS, vol. 5147, pp. 65–80. Springer, Heidelberg (2008)
Chen, H., De, A., Goel, A.: Towards Programmable Molecular Machines. In: Foundations of Nanoscience (FNANO) (2008)
Danos, V., Feret, J., Fontana, W., Harmer, R., Krivine, J.: Rule-based modelling of cellular signalling. In: Caires, L., Li, L. (eds.) CONCUR 2007. LNCS, vol. 4703, pp. 17–41. Springer, Heidelberg (2007)
Kurtz, S., Mahaney, S., Royer, J., Simon, J.: Biological computing. In: Complexity Theory Retrospective II, pp. 179–195 (1997)
Landauer, R.: Irreversibility and heat generation in the computing process. IBM Journal of Research and Development 5(3), 183–191 (1961)
Liekens, A.M.L., Fernando, C.T.: Turing complete catalytic particle computers. In: Almeida e Costa, F., Rocha, L.M., Costa, E., Harvey, I., Coutinho, A. (eds.) ECAL 2007. LNCS (LNAI), vol. 4648, pp. 1202–1211. Springer, Heidelberg (2007)
Minsky, M.L.: Computation: finite and infinite machines. Prentice-Hall, Englewood Cliffs (1967)
Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible Turing machine. The Transactions of the IEICE E 72(3), 223–228 (1989)
Qian, L., Winfree, E.: A simple DNA gate motif for synthesizing large-scale circuits. In: Goel, A., Simmel, F.C., Sosík, P. (eds.) DNA 14. LNCS, vol. 5347, pp. 70–89. Springer, Heidelberg (2009)
Rothemund, P.: A DNA and restriction enzyme implementation of Turing machines. In: Lipton, R., Baum, E. (eds.) DNA Based Computers. DIMACS, vol. 27, pp. 75–119. AMS, Providence (1996)
Rothemund, P., Papadakis, N., Winfree, E.: Algorithmic self-assembly of DNA sierpinski triangles. PLoS Biology 2(12), e424 (2004)
Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314(5805), 1585–1588 (2006)
Smith, W.: DNA computers in vitro and vivo. In: Lipton, R., Baum, E. (eds.) DNA Based Computers. DIMACS, vol. 27, pp. 121–185. AMS, Providence (1996)
Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Natural Computing 7(4), 615–633 (2008)
Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proceedings of the National Academy of Science 107(12), 5393–5398 (2010)
Winfree, E.: On the computational power of DNA annealing and ligation. In: Lipton, R., Baum, E. (eds.) DNA Based Computers. DIMACS, vol. 27, pp. 199–221. AMS, Providence (1996)
Winfree, E.: Simulations of computing by self-assembly. Technical Report CS-TR:1998.22, Caltech (1998)
Yin, P., Turberfield, A., Sahu, S., Reif, J.: Design of an autonomous DNA nanomechanical device capable of universal computation and universal translational motion. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 10. LNCS, vol. 3384, pp. 426–444. Springer, Heidelberg (2005)
Zhang, D., Turberfield, A., Yurke, B., Winfree, E.: Engineering entropy-driven reactions and networks catalyzed by DNA. Science 318(5853), 1121–1125 (2007)
Zhang, D., Winfree, E.: Control of DNA strand displacement kinetics using toehold exchange. Journal of the American Chemical Society 131(47), 17303–17314 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Qian, L., Soloveichik, D., Winfree, E. (2011). Efficient Turing-Universal Computation with DNA Polymers. In: Sakakibara, Y., Mi, Y. (eds) DNA Computing and Molecular Programming. DNA 2010. Lecture Notes in Computer Science, vol 6518. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18305-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-18305-8_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-18304-1
Online ISBN: 978-3-642-18305-8
eBook Packages: Computer ScienceComputer Science (R0)