Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.07099 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913584160702464 |
|---|---|
| author | Calabrese, Kim Doty, David |
| author_facet | Calabrese, Kim Doty, David |
| contents | We study the model of continuous chemical reaction networks (CRNs), consisting of reactions such as $A+B \to C+D$ that can transform some continuous, nonnegative real-valued quantity (called a *concentration*) of chemical species $A$ and $B$ into equal concentrations of $C$ and $D$. Such a reaction can occur from any state in which both reactants $A$ and $B$ are present, i.e., have positive concentration. We modify the model to allow *inhibitors*, for instance, reaction $A+B \to^{I} C+D$ can occur only if the reactants $A$ and $B$ are present and the inhibitor $I$ is absent. The computational power of non-inhibitory CRNs has been studied. For instance, the reaction $X_1+X_2 \to Y$ can be thought to compute the function $f(x_1,x_2) = \min(x_1,x_2)$. Under an "adversarial" model in which reaction rates can vary arbitrarily over time, it was found that exactly the continuous, piecewise linear functions can be computed, ruling out even simple functions such as $f(x) = x^2$. In contrast, in this paper we show that inhibitory CRNs can compute any computable function $f:\mathbb{N}\to\mathbb{N}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_07099 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Rate-independent continuous inhibitory chemical reaction networks are Turing-universal Calabrese, Kim Doty, David Emerging Technologies We study the model of continuous chemical reaction networks (CRNs), consisting of reactions such as $A+B \to C+D$ that can transform some continuous, nonnegative real-valued quantity (called a *concentration*) of chemical species $A$ and $B$ into equal concentrations of $C$ and $D$. Such a reaction can occur from any state in which both reactants $A$ and $B$ are present, i.e., have positive concentration. We modify the model to allow *inhibitors*, for instance, reaction $A+B \to^{I} C+D$ can occur only if the reactants $A$ and $B$ are present and the inhibitor $I$ is absent. The computational power of non-inhibitory CRNs has been studied. For instance, the reaction $X_1+X_2 \to Y$ can be thought to compute the function $f(x_1,x_2) = \min(x_1,x_2)$. Under an "adversarial" model in which reaction rates can vary arbitrarily over time, it was found that exactly the continuous, piecewise linear functions can be computed, ruling out even simple functions such as $f(x) = x^2$. In contrast, in this paper we show that inhibitory CRNs can compute any computable function $f:\mathbb{N}\to\mathbb{N}$. |
| title | Rate-independent continuous inhibitory chemical reaction networks are Turing-universal |
| topic | Emerging Technologies |
| url | https://arxiv.org/abs/2403.07099 |