Editing Open Problems (section)

= Composability of CRNs =

===Context===
Suppose we wish to compose two computing CRNs whose input and output are the same format (e.g., both are Boolean, or both are real numbers), so that the output of an upstream CRN $\mathcal{U}$ can be supplied as input to a downstream CRN $\mathcal{D}$. In contrast to more traditional models of computation, composition in CRNs is not straightforward to implement, since there is in general no way for $\mathcal{U}$ to signal that it is finished computing so that $\mathcal{D}$ can remain "off" until $\mathcal{U}$ is done.

Several tricks in different models of CRN computation have been developed for enabling composition:
<ul>
<li> '''Monotone production of outputs:''' If $\mathcal{U}$ only produces but never consumes its output, then it may be composed with $\mathcal{D}$ unmodified. This is because $\mathcal{D}$ must already be designed to account for the fact that it may take arbitrarily long to encounter all of its input. From the point of view of $\mathcal{D}$, there is no difference between a "shy" input that takes a very long time until its first reaction, and an input that will be produced eventually by $\mathcal{U}$ but simply has not yet been produced. Also, since $\mathcal{U}$ never consumes its output, $\mathcal{D}$ will not interfere with $\mathcal{U}$ by consuming $\mathcal{U}$'s output. Nonmonotone functions such as $f(x_1,x_2) = x_1-x_2$, although computable by a CRN such as $X_1 \to Y;\ \ X_2 + Y \to \emptyset$, cannot be computed by a CRN that does not consume its output. In these cases, a common trick is to use a "dual-rail" representation, representing the output (and in the case of $\mathcal{D}$, the input) by ''two'' species $Y^+$ and $Y^-$, such that we interpret the "output" of the CRN to be the ''difference'' between the two counts $\# Y^+ - \# Y^-$. In this case, it is possible to decrease the output by producing $Y^-$, enabling monotone production of output species even for functions that are not monotone. (In the example, the reactions $X_1 \to Y^+$ and $X_2 \to Y^-$ compute the function $f(x_1,x_2) = x_1-x_2$.)

<li> '''Halting signal:''' If $\mathcal{U}$ is able to sense that it is done, then this gives an easy way to compose. More precisely, if there is a species $H$ that is absent initially, and $\mathcal{U}$ can be designed to produce $H$ only if the output is correct, then by letting $H$ "activate" $\mathcal{D}$ (e.g., by being a catalyst in all of $\mathcal{D}$'s reactions, or by a reaction $H \to L$, where $L$ is necessary to initiate the first reaction of $\mathcal{D}$), $\mathcal{D}$ can remain "off" until $\mathcal{U}$ is done, and they will not interfere with each other.

<li> '''Catalytic inputs:''' This is, in a sense, complementary to the "monotone production of outputs" technique. If $\mathcal{D}$ only uses its input species as catalysts (thus never altering their counts), then $\mathcal{D}$ cannot interfere with $\mathcal{U}$ since $\mathcal{D}$ cannot alter the species they share in common. However, this means that $\mathcal{D}$ cannot deterministically sense ''how much'' of its inputs it has, only whether they are present or absent. (It could also stochastically sense their amounts since the rate of a reaction like $X_1 + A \to X_1 + B$ would be higher if $X_1$ has higher count.) An example of this idea in action is the following generic way to create any two-input, one-output Boolean gate with four reactions (the reactions essentially give the truth table of the gate). For example, to compute AND (call the input wires $x$ and $y$ and the output wire $z$):
$$
0_x + 0_y + 1_z \to 0_x + 0_y + 0_z
\\
0_x + 1_y + 1_z \to 0_x + 1_y + 0_z
\\
1_x + 0_y + 1_z \to 1_x + 0_y + 0_z
\\
1_x + 1_y + 0_z \to 1_x + 1_y + 1_z
$$
In other words, if two inputs encounter the wrong output, they catalytically convert it to the correct output.
</ul>

=== Problem statement ===
Give a general construction to make a CRN computing a function composable. The details of what that means precisely will depend on the precise definition of "a CRN computing a function".

=== Interested Participants ===

* [[User:Doty | Dave Doty ]]
* [[User:Brijder | Robert Brijder ]]