A Caltech Library Service

Probability 1 Computation with Chemical Reaction Networks

Cummings, Rachel and Doty, David and Soloveichik, David (2014) Probability 1 Computation with Chemical Reaction Networks. In: DNA Computing and Molecular Programming. Lecture Notes in Computer Science. No.8727. Springer , Cham, pp. 37-52. ISBN 978-3-319-11294-7.

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

Use this Persistent URL to link to this item:


The computational power of stochastic chemical reaction networks (CRNs) varies significantly with the output convention and whether or not error is permitted. Focusing on probability 1 computation, we demonstrate a striking difference between stable computation that converges to a state where the output cannot change, and the notion of limit-stable computation where the output eventually stops changing with probability 1. While stable computation is known to be restricted to semilinear predicates (essentially piecewise linear), we show that limitstable computation encompasses the set of predicates in Δ^0_2 in the arithmetical hierarchy (a superset of Turing-computable). In finite time, our construction achieves an error-correction scheme for Turing universal computation. This work refines our understanding of the tradeoffs between error and computational power in CRNs.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access ItemJournal Article
Doty, David0000-0002-3922-172X
Soloveichik, David0000-0002-2585-4120
Additional Information:© 2014 Springer International Publishing Switzerland. We thank Shinnosuke Seki, Chris Thachuk, and Luca Cardelli for many useful and insightful discussions. The first author was supported by NSF grants CCF-1049899 and CCF-1217770, the second author was supported by NSF grants CCF-1219274 and CCF-1162589 and the Molecular Programming Project under NSF grant 1317694, and the third author was supported by NIGMS Systems Biology Center grant P50 GM081879.
Funding AgencyGrant Number
NIHP50 GM081879
Series Name:Lecture Notes in Computer Science
Issue or Number:8727
Record Number:CaltechAUTHORS:20160620-142150323
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:68540
Deposited By: Tony Diaz
Deposited On:21 Jun 2016 23:38
Last Modified:11 Nov 2021 04:01

Repository Staff Only: item control page