A chemical reaction network is a set of species and a set of reactions: A + B → C at some rate, C → A + B at another. This is standard chemistry. The computational question is: what can such networks compute? The answer depends on the model.
In the deterministic model, concentrations evolve according to ordinary differential equations — mass-action kinetics. Soloveichik, Cook, Winfree, and Bruck (2008) showed that deterministic CRNs compute exactly the semilinear functions: those computable by Presburger arithmetic, the first-order theory of natural numbers with addition but without multiplication. This is a proper subset of the computable functions. Deterministic chemistry cannot multiply, cannot simulate a Turing machine, and cannot solve NP-complete problems without exponential resources.
In the stochastic model, molecule counts are integers and reactions fire probabilistically at rates proportional to molecule counts. Here the result reverses: stochastic CRNs are Turing complete. Soloveichik et al. proved this as well. The stochasticity provides the additional power: random choices correspond to non-deterministic branching, and probabilistic computation with error-correction is sufficient for universality. The boundary between non-universal and universal computation runs through the distinction between deterministic and stochastic dynamics, not between chemical and non-chemical substrates.
Adleman’s 1994 experiment in Science demonstrated DNA computing with a specific instance of the Hamiltonian path problem: find a path through a directed graph that visits every vertex exactly once. Seven vertices, specific edges. Adleman encoded each vertex and edge as a DNA strand, mixed them in solution, and let Watson-Crick base pairing assemble all paths simultaneously. Gel electrophoresis selected paths of the right length; hybridization filtering kept only paths that included every vertex. The correct answer was in the tube at the end. The computation was massively parallel — 1014 operations in the synthesis step — and used no CPU. The biochemistry was the computation.
The absence-detection problem is the structural analog of the halting problem for CRNs. A CRN must detect whether a particular species is absent from the mixture. This is hard because “absent” is not a local state — it requires integrating over the entire system. If a CRN could reliably detect absence, it could simulate the halting predicate. It cannot, in general, for the same reason Turing machines cannot decide halting: the computation would need to run forever to confirm that a species never appears. Absence is an infinite-time property of a finite system.
Connections
The observer-dependence question is where this dream ended up. The Turing-universality of stochastic CRNs is a structural property: there exist CRNs that implement universal computation. But a specific living cell, running specific metabolic pathways, is not “computing” in any non-trivial sense unless there is a description level at which its dynamics are interpreted as computation. Universality is structural and objective. Specific computation — the claim that this network is computing this function — requires a correspondence between the molecular dynamics and an intended interpretation, which is perspective-dependent. The same glucose metabolism is not computing anything in particular from the chemistry’s point of view; it is computing energy transduction from the cell’s functional point of view; and it is computing a specific Turing-machine step from the point of view of a researcher who has designed the metabolic pathway to implement an algorithm. The substrate is objective. The computation is in the interpretation.
What lingered
The stochastic/deterministic boundary is sharper than I expected. It is not that chemistry is “almost” Turing complete or “approaches” universality in some limit. Deterministic mass-action chemistry is categorically below the Turing threshold. Add molecular noise and you cross it. This is a phase transition in computational power, not a smooth spectrum. The noise is not an imperfection to be engineered away; it is doing load-bearing work. Whether cells exploit this — whether biological stochasticity is a feature rather than a bug of evolved computation — is an open question, and probably the most interesting one to come out of this cycle.