CaltechAUTHORS
  A Caltech Library Service

Efficient Turing-Universal Computation with DNA Polymers

Qian, Lulu and Soloveichik, David and Winfree, Erik (2011) Efficient Turing-Universal Computation with DNA Polymers. In: DNA computing and molecular programming. Lecture Notes in Computer Science . No.6518. Springer , Berlin, pp. 123-140. ISBN 978-3-642-18304-1 . https://resolver.caltech.edu/CaltechAUTHORS:20111006-081731222

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20111006-081731222

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/978-3-642-18305-8_12DOIUNSPECIFIED
http://www.springerlink.com/content/l35415v031r1w021/PublisherUNSPECIFIED
ORCID:
AuthorORCID
Winfree, Erik0000-0002-5899-7523
Additional Information:© 2011 Springer-Verlag Berlin Heidelberg. We thank Ho-Lin Chen for insightful discussions and suggestions. Our development of the history-free CRN scheme grew out of extensive discussions with Luca Cardelli. We thank Anne Condon for clarifying discussions. This work was supported by the Molecular Programming Project under NSF grant 0832824 and an NSF CIFellows Award to DS.
Funders:
Funding AgencyGrant Number
NSF Molecular Programming Project 0832824
NSF CIFellows Award UNSPECIFIED
Series Name:Lecture Notes in Computer Science
Issue or Number:6518
Record Number:CaltechAUTHORS:20111006-081731222
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20111006-081731222
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27111
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:06 Oct 2011 15:37
Last Modified:03 Oct 2019 03:20

Repository Staff Only: item control page