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 $$\phi :{\mathbb {N}}\rightarrow \{0,1\}$$?:N?{0,1} in $$\Delta ^0_2$$Δ20 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:{\mathbb {N}}\rightarrow {\mathbb {N}}$$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.
['Rachel Cummings', 'David Doty', 'David Soloveichik']
Probability 1 computation with chemical reaction networks