CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20160620-093414531

[img] PDF - Submitted Version
See Usage Policy.

450kB

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

Abstract

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
https://doi.org/10.1007/s11047-015-9501-xDOIArticle
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSFCCF-1049899
NSFCCF-1217770
NSFCCF-1219274
NSFCCF-1162589
NSFCCF-1317694
NIHP50 GM081879
Subject Keywords:Arithmetical hierarchy – Chemical reaction network – Deterministic computation – Probabilistic computation
Issue or Number:2
DOI:10.1007/s11047-015-9501-x
Record Number:CaltechAUTHORS:20160620-093414531
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160620-093414531
Official Citation:Cummings, R., Doty, D. & Soloveichik, D. Probability 1 computation with chemical reaction networks. Nat Comput 15, 245–261 (2016). https://doi.org/10.1007/s11047-015-9501-x
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:68517
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:20 Jun 2016 17:14
Last Modified:11 Nov 2021 04:01

Repository Staff Only: item control page