Editing Open Problems (section)

=== Problem context ===

The standard notion of "stable computation" with CRNs<ref name="CDS2013"/> says that a CRN computes a function $f:\mathbb{N}^k \to \mathbb{N}$ (the concept also makes sense with computing predicates $\phi:\mathbb{N}^k \to \{0,1\}$) if, for every state $\vec{c}$ reachable from the initial state $\vec{x}$, there is a correct "output stable" state $\vec{o}$ reachable from $\vec{c}$. Here, to say that $\vec{o}$ is output stable means that the count of the output species $Y$ cannot change (no reaction producing or consuming $Y$ is possible in $\vec{o}$ or in any state reachable from $\vec{o}$). To say that it is correct means that the count of $Y$ is equal to the intended output $f(\vec{x})$.

One property to observe is that the definition does not capture any notion of the CRN "knowing" when it has computed the correct answer. In the case of functions, the count of $Y$ changes as reactions occur, and eventually it stops changing, but there is no signal that the CRN gives to indicate that the count of $Y$ has stabilized. In the case of predicates, some of the species "vote" for a YES or NO answer, and eventually all the voters are unanimous and correct, but the CRN does not signal that the voters have stabilized.

One could imagine making an additional requirement of the CRN: there is a special molecule $H$ (the "halt" molecule), so that the count of $H$ is initially 0, the CRN is guaranteed eventually to produce $H$, and it is guaranteed that $H$ will not be produced until the answer has stabilized to the correct value. This would enable CRNs to be more easily composed, for example, since a downstream CRN could have its computation triggered by the $H$ molecule of an upstream CRN, to guarantee that they do not execute simultaneously and interfere with each other.

Unfortunately, in the case of total functions, this is impossible for stable computation of nontrivial functions or predicates. In particular, if there are two inputs $\vec{x}_1 < \vec{x}_2$ such that $f(\vec{x}_1) \neq f(\vec{x}_2)$, then there is a sequence of reactions from $\vec{x}_1$ that leads to state $\vec{o}_1$ with $\vec{o}_1(H) > 0$, and since $\vec{x}_1 < \vec{x}_2$, that sequence of reactions is applicable to $\vec{x}_2$, but since $f(\vec{x}_1) \neq f(\vec{x}_2)$ this means it is possible to produce $H$ from $\vec{x}_2$ before the CRN has stabilized to the correct answer $f(\vec{x}_2)$.

However, if $f:\mathbb{N}^k \dashrightarrow \mathbb{N}$ is a partial function, then it is possible for $\mathrm{dom}\ f$ to have all its elements be pairwise incomparable: $(\forall \vec{x}_1, \vec{x}_2 \in \mathrm{dom}\ f)\ \vec{x}_1 \not < \vec{x}_2$. So-called "dual-rail" representations of inputs to Boolean predicates $\phi: \{0,1\}^k \to \{0,1\}$, in which the $i$'th bit is represented in the initial state $\vec{x}$ by two species $1_i$ and $0_i$: $\vec{x}(1_i) = 1$ and $\vec{x}(0_i) = 0$ to represent that the $i$'th bit is 1, and $\vec{x}(1_i) = 0$ and $\vec{x}(0_i) = 1$ to represent that the $i$'th bit is 0. Therefore the set of CRN input states (a vector in $\N^{2k}$ since there are two species to represent each of the $k$ input bits to $\phi$) is pairwise incomparable.

In particular, any Boolean predicate $\phi: \{0,1\}^k \to \{0,1\}$ on a fixed number of input can be stably computed by a CRN, producing molecule $H$ precisely when the output stabilizes. With a standard "indicator" representation (one species $1_i$ to represent the $i$'th input bit), this is impossible for some predicates due to the pairwise comparability of some input states.