Reverse-Robust Computation with Chemical Reaction Networks
Pith reviewed 2026-05-10 11:18 UTC · model grok-4.3
The pith
All semilinear predicates and functions can be stably computed by chemical reaction networks even when reactions remain reversible up to a finite cutoff.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Under the reverse-robust computation model for CRNs, where reactions can occur in either direction up to a cutoff and only forward thereafter, all semilinear predicates and semilinear functions remain computable, and prior constructions for the irreversible case suffice.
What carries the argument
Invariants defined as linear or linear-modulo-m combinations of species counts that remain unchanged by all reactions, used to prove that computations reach the correct stable state before the irreversibility cutoff.
If this is right
- Existing CRN constructions for semilinear computation apply directly to the reverse-robust model without modification.
- CRN computations tolerate limited reversibility while preserving correctness for any semilinear predicate or function.
- Stable states are reached while invariants hold, ensuring the output is correct independent of reverse reactions before the cutoff.
- Any semilinear function or predicate has a CRN implementation that works under partial reversibility.
Where Pith is reading between the lines
- Real chemical implementations may achieve theoretical computational power if a natural cutoff arises from rate differences.
- Invariant-based proofs could adapt to other models allowing partial reversibility in molecular computation.
- The same approach might identify which computations beyond semilinear sets become feasible or fail under reverse-robust rules.
Load-bearing premise
There exists a finite cutoff after which all reactions become irreversible and the computation reaches a stable state by that time while preserving the invariants.
What would settle it
A specific semilinear predicate or function for which every existing CRN construction produces an incorrect stable output when reactions are allowed to reverse before a cutoff, or an invariant that changes under the allowed reversible reactions.
read the original abstract
Chemical reaction networks, or CRNs, are known to stably compute semilinear Boolean-valued predicates and functions, provided that all reactions are irreversible. However, this property does not hold for wet-lab implementations, as all chemical reactions are reversible, even at very slow rates. We study the computational power of CRNs under the reverse-robust computation model, where reactions are permitted to occur either in forward or in reverse up to a cutoff point, after which they may only occur in forward. Our main results show that all semilinear predicates and all semilinear functions can be computed reverse-robustly, and in fact, that existing constructions continue to hold under the reverse-robust computational model. A key tool used to prove correctness under the reverse-robust computation model is invariants: linear (or linear modulo some $m$) combinations of the counts of the species that are preserved by all reactions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the reverse-robust computation model for chemical reaction networks (CRNs), allowing reactions to proceed forward or reverse until a finite cutoff after which only forward reactions occur. It claims that all semilinear predicates and all semilinear functions remain computable in this model, and that standard irreversible CRN constructions continue to work without change. The proofs rely on linear (or modulo-m) invariants preserved by reaction stoichiometry, which constrain reachable states identically in the bidirectional phase.
Significance. If correct, the result is significant for bridging theoretical CRN computation with laboratory realities, where reversibility is unavoidable. By proving that existing semilinear constructions are robust to a finite reversible phase, the work shows that the computational power does not degrade and that invariants suffice to guarantee correctness up to and after the cutoff. This strengthens the case for CRNs as a model of computation with direct wet-lab relevance, using a standard rigorous technique (invariant preservation) that applies equally to bidirectional steps.
minor comments (4)
- §2 (model definition): The precise relationship between the cutoff time and the point at which the CRN reaches a forward-stable state should be stated more explicitly, including whether the cutoff is chosen uniformly or depends on the input size.
- §4 (predicate constructions): While the invariant argument is sketched, an explicit statement that every forward-stable state in the post-cutoff phase encodes the correct output (via the invariant) would make the reduction from the irreversible case fully transparent.
- Notation: The paper uses both 'linear invariants' and 'linear modulo m' without a single consolidated definition; a short preliminary subsection collecting the invariant forms used in each theorem would improve readability.
- References: The discussion of prior semilinear CRN results would benefit from citing the specific constructions (e.g., the original Angluin et al. or Soloveichik et al. papers) that are being shown to remain valid.
Simulated Author's Rebuttal
We thank the referee for the positive and accurate summary of our paper, as well as the recommendation for minor revision. We are pleased that the significance for connecting theoretical CRN computation to laboratory realities was recognized.
Circularity Check
No significant circularity; derivation self-contained
full rationale
The paper's central result is that existing CRN constructions for semilinear predicates and functions remain correct under the reverse-robust model. This follows directly from the fact that linear (or mod-m) invariants on species counts are preserved by the stoichiometry of every reaction, whether executed forward or backward. Because both directions preserve the same invariants, the set of states reachable before the cutoff is still restricted to the correct equivalence class; the irreversible phase after cutoff then reaches a stable output fixed by that invariant. The invariants are a standard, externally verifiable property of CRN reaction vectors and do not depend on the new model or on any fitted parameters. No step equates a derived quantity to its own input by definition, renames a known result, or relies on a load-bearing self-citation whose validity is assumed rather than shown. The argument is therefore independent of the paper's own prior results beyond the standard semilinear constructions, which are treated as given external facts.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Linear combinations of species counts are preserved by all reactions (forward and reverse).
- domain assumption Semilinear predicates and functions are computable by irreversible CRNs via known constructions.
Reference graph
Works this paper leans on
-
[1]
URL:https://doi.org/10.1007/s00446-005-0138-3,doi:10.1007/S00446-005-0138-3. 2 Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks.Nat. Comput., 13(4):517–534,
-
[2]
Deterministic function computation with chemical reaction networks
URL:https://doi.org/10. 1007/s11047-013-9393-6,doi:10.1007/S11047-013-9393-6. 3 David Doty and Monir Hajiaghayi. Leaderless deterministic chemical reaction networks. Nat. Comput., 14(2):213–223,
-
[3]
URL:https://doi.org/10.1007/s11047-014-9435-8, doi:10.1007/S11047-014-9435-8. 4 David Doty and Ben Heckmann. The computational power of discrete chemical reaction networks with bounded executions. In Dan Alistarh, editor,38th International Symposium on Distributed Computing, DISC 2024, Madrid, Spain, October 28 - November 1, 2024, LIPIcs, pages 20:1–20:15...
-
[4]
URL: https://doi.org/10.4230/LIPIcs.DISC.2024.20,doi:10.4230/LIPICS.DISC.2024.20
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.