A Caltech Library Service

Probability 1 computation with chemical reaction networks

Cummings, Rachel and Doty, David and Soloveichik, David (2016) Probability 1 computation with chemical reaction networks. Natural Computing, 15 (2). pp. 245-261. ISSN 1567-7818. doi:10.1007/s11047-015-9501-x.

[img] PDF - Submitted Version
See Usage Policy.


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 limit-stable computation encompasses the set of predicates ϕ:N→{0,1} 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. We show an analogous characterization of the functions f:N→N computable by CRNs with probability 1, which encode their output into the count of a certain species. This work refines our understanding of the tradeoffs between error and computational power in CRNs.

Item Type:Article
Related URLs:
URLURL TypeDescription
Doty, David0000-0002-3922-172X
Soloveichik, David0000-0002-2585-4120
Additional Information:© 2016 Springer Netherlands. We thank Damien Woods and Niranjan Srinivas for many useful discussions, Monir Hajiaghayi for pointing out a problem in an earlier version of this paper, and anonymous reviewers for helpful suggestions. 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
Subject Keywords:Arithmetical hierarchy – Chemical reaction network – Deterministic computation – Probabilistic computation
Issue or Number:2
Record Number:CaltechAUTHORS:20160620-093414531
Persistent URL:
Official Citation:Cummings, R., Doty, D. & Soloveichik, D. Probability 1 computation with chemical reaction networks. Nat Comput 15, 245–261 (2016).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:68517
Deposited By: Tony Diaz
Deposited On:20 Jun 2016 17:14
Last Modified:11 Nov 2021 04:01

Repository Staff Only: item control page