Speed faults in computation by chemical reaction networks
∗
Ho-Lin Chen
†
Rachel Cummings
‡
David Doty
§
David Soloveichik
¶
Abstract
Chemical reaction networks (CRNs) formally model chemistry in a well-mixed solution. As-
suming a fixed molecular population size and bimolecular reactions, CRNs are formally equiva-
lent to population protocols, a model of distributed computing introduced by Angluin, Aspnes,
Diamadi, Fischer, and Peralta (PODC 2004). The challenge of fast computation by CRNs (or
population protocols) is to ensure that there is never a bottleneck “slow” reaction that requires
two molecules (agent states) to react (communicate), both of which are present in low (
O
(1))
counts. It is known that CRNs can be fast in expectation by avoiding slow reactions with high
probability. However, states may be reachable (with low probability) from which the correct
answer may only be computed by executing a slow reaction. We deem such an event a
speed
fault
. We show that the problems decidable by CRNs guaranteed to avoid speed faults are
precisely the
detection problems
: Boolean combinations of questions of the form “is a certain
species present or not?”. This implies, for instance, that no speed fault free CRN could decide
whether there are at least two molecules of a certain species, although a CRN could decide this
in “fast” expected time — i.e. speed fault free CRNs “can’t count.”
1 Introduction
Understanding the principles of molecular computation is essential to making sense of information
processing in biological cellular regulatory networks. Further, in engineering of life-like devices
(e.g. “wet robots” that can patrol the blood for cancer cells) we are rapidly approaching the point
where we are limited by conceptual understanding: How molecular networks can be programmed
to process information and carry out computation subject to the natural constraints of aqueous
chemistry is still not well-understood.
A foundational model of chemistry commonly used in natural sciences is that of chemical re-
action networks (CRNs), i.e., (finite) sets of chemical reactions such as
A
+
B
→
A
+
C
. Subject
to discrete semantics (integer number of molecules) the model corresponds to a continuous time,
discrete state, Markov process [12]. A state of the system is a vector of non-negative integers spec-
ifying the molecular counts of the species (e.g.,
A
,
B
,
C
), a reaction can occur only when all its
reactants are present, and transitions between states correspond to reactions (i.e., when the above
reaction occurs the count of
B
is decreased by 1 and the count of
C
increased by 1). The transi-
tion rate is proportional to the product of the counts of the reactants. CRNs are widely used to
∗
The third, and fourth authors were supported by the Molecular Programming Project under NSF grants 0832824
and 1317694, the first author was supposed by NSC grant number 101-2221-E-002-122-MY3, the second author
was supported by NSF grants CCF-1049899 and CCF-1217770, the third author was supported by a Computing
Innovation Fellowship under NSF grant 1019343, NSF grants CCF-1219274 and CCF-1162589, and the fourth author
was supported by NIGMS Systems Biology Center grant P50 GM081879.
†
National Taiwan University, Taipei, Taiwan,
holinc@gmail.com
‡
California Institute of Technology, Pasadena, CA, USA,
rachelc@u.northwestern.edu
.
§
California Institute of Technology, Pasadena, CA, USA,
ddoty@caltech.edu
¶
University of California, San Francisco, San Francisco, CA, USA,
david.soloveichik@ucsf.edu
1
describe natural biochemical systems such as the intricate cellular regulatory networks responsible
for the information processing within cells. With recent advances in synthetic biology, CRNs are
a promising language for the design of artificial biochemical networks. For example, the physical
primitive of nucleic-acid strand displacement cascades provides concrete chemical implementations
of arbitrary CRNs [4, 8, 17]. Thus, since in principle any CRN can be built, hypothetical CRNs
with interesting behaviors are becoming of more than theoretical interest.
The importance of the CRN model is underscored by the observation that intimately related
models repeatedly arise in theoretical computer science under different guises: e.g. vector addition
systems [13], Petri nets [15], population protocols [1]. The connection to distributed computing
models, in turn, resulted in novel insights regarding natural cellular regulatory networks [5].
Parallelism is a basic attribute of chemistry, and one that is of central importance in understand-
ing molecular information processing. This kind of parallelism is both a blessing and a curse: it
can be used to speed up computation, but we must be careful to avoid “race conditions” (reactions
happening in an unintended order) which may lead to error.
a)
e)
b)
f)
c)
g)
d)
parallelizable
deterministic
parallelizable
deterministic
Y
iff [at least 1 molecule of
A
1
and at least 1 molecule of
A
2
]
Y
iff [at least 2 molecules of
A
]
Figure 1:
Two molecular computation tasks: predicates
“Is there at least 1 molecule of
A
1
and at least one molecule
of
A
2
?” (left), and “Are there at least 2 molecules of
A
?”
(right). CRNs (a)-(d) compute the first predicate (left),
and CRNs (e)-(g) compute the second (right). Parameter
n
is the initial amount of
F
, or
F
1
and
F
2
species which
help in the computation. Informally the parallelizeable
CRNs are those that produce the output faster with in-
creasing
n
. Deterministic CRNs are those that compute
correctly no matter what order the reactions happen to
occur in. Other strategies (not shown) involve producing
Y
but consuming it if the predicate is not satisfied.
Consider a very basic task: a chemi-
cal system (e.g. cell) responding to molec-
ular signals present in very small quanti-
ties. More specifically, say the computation
is to produce at least one molecule of
Y
if
and only if there is at least one molecule
of species
A
1
and at least one molecule of
species
A
2
. Consider the strategy shown in
Fig 1(b). Intuitively, this corresponds to
having receptors
F
that in order to activate
need to bind both
A
1
and
A
2
. By having
n
receptors
F
we can increase the rate of
the first reaction, but if there is only one
molecule of
A
1
, there will be at most one
molecule of
F
′
and thus the second reaction
occurs at a rate independent of the amount
of receptor. Thus this scheme is “not par-
allelizeable”.
1
A better strategy is to amplify the signal
before taking the conjunction: e.g. Fig 1(c).
Here the receptors release
A
1
back upon in-
teracting with it, and a single
A
1
can inter-
act with many receptors (converting them
from
F
to
F
′
). Intuitively, the more recep-
tors
F
we have, the faster we’ll get a large
number of
F
′
’s, and the faster the
Y
will
get produced via the second reaction. More specifically, observe that starting with
n >
0 molecules
of
F
, and a molecule of
A
1
and
A
2
each, the reachable states without
Y
are: for 0
≤
m
≤
n
,
((
n
−
m
)
F, m F
′
,
1
A
1
,
1
A
2
). From any reachable state without
Y
, we can reach
Y
through
1
Bimolecular reaction rates scale inversely with the total volume, and it is impossible to fit arbitrarily many
molecules in a fixed volume. While for large enough molecular counts we will run into this finite density constraint,
we study the scaling of speed with molecular count before that point is reached. An alternate perspective is that our
task is to compute as quickly as possible in volume sufficient to allow molecules of
F
to fill the volume with constant
density [16].
2
a sequence of reaction executions where one of the reactants is present in at least
b
n
1
/
2
c
count,
2
and under stochastic chemical kinetics, the expected time to traverse this path is
O
(1
/n
1
/
2
) —
decreasing with
n
.
3
Scheme Fig 1(d) is even faster: it can be shown that from any reachable state,
the expected time to produce
Y
scales as
O
(log
n/n
).
Now consider a slightly different computational task: produce at least one molecule of
Y
if
and only if there are at least 2 molecules of species
A
. The natural analog of Fig 1(b) fails to be
deterministic: the reactions
A
+
F
→
F
′
,
A
+
F
′
→
Y
suffer from a “race condition” where
Y
is
never produced if both molecules of
A
happen to react with
F
. This can be fixed by having the
receptor
F
bind
A
reversibly
4
as in Fig. 1(f). However, this scheme is not parallelizeable for the
same reason as (b).
The natural analog of the parallelizeable reaction scheme Fig 1(c) will not solve this task
correctly at all: With reactions
A
+
F
→
F
′
+
A
,
A
+
F
′
→
Y
, even a single molecule of
A
will
always lead to a
Y
.
Also problematic is the scheme shown in Fig 1(g) based on (d). While it is parallelizeable, it
also suffers from a race condition that can result in an error. If the two molecules of
A
happen
to react with different receptor types (
F
1
and
F
2
) then
Y
will be produced. However, if both
A
’s
react with the same receptor type,
Y
will never be produced.
Informally, our main result is that no CRN is deterministic and parallelizeable at the same time
for the “2
A
problem” (or any computation that involves counting, rather than simply detecting
the presence or absence of input species). Thus deterministic and parallelizeable must be disjoint in
Fig. 1(right). Unlike the examples above, we allow a broader range of schemes that could produce
and consume
Y
repeatedly but eventually converge on the presence or absence of
Y
as the output. In
order to define “parallelizeable” formally, we introduce the notion of a “speed fault”. A speed fault
occurs if a state is reached such that to stabilize to the correct output from that state requires using
a bimolecular reaction with both reactants bounded independently of
n
. Thus “deterministically
parallelizeable” corresponds to speed fault free. Our main result is that the problems decidable by
speed fault free CRNs are precisely the
detection problems
: Boolean combinations of questions of
the form “is a certain species present or not?”. Thus speed fault free CRNs “can’t count.”
The current work stems from the desire to understand fast deterministic computation in CRNs
and population protocols. While sophisticated chemical algorithms and protocols have been de-
veloped to compute a large class of functions quickly and without error (see next section), most
constructions are not deterministically fast in the same strong sense as they are deterministic.
Indeed, deterministic computation is a worst case notion that intuitively ensures correctness no
matter what unlucky sequence of reactions occurs. However, fast computation is defined with re-
spect to large probability reaction sequences. Our definition captures the natural worst case notion
of speed.
5
2
If
m <
b
n
1
/
2
c
, execute the first reaction
b
n
1
/
2
c−
m
times (resulting in
b
n
1
/
2
c
molecules of
F
′
), and then execute
the second reaction. If
m
≥b
n
1
/
2
c
, execute the second reaction.
3
The rate of a bimolecular reaction is proportional to the product of the counts of the reactants. Thus the expected
time from the state with
m <
b
n
1
/
2
c
molecules of
F
′
to reach the state with
b
n
1
/
2
c
molecules of
F
′
is proportional
to
∑
b
n
1
/
2
c
i
=
m
1
/
(
n
−
i
)
≤
n
1
/
2
·
1
/
(
n
−
n
1
/
2
) =
O
(1
/n
1
/
2
). Finally the rate of the second reaction when there are
b
n
1
/
2
c
molecules of
F
′
is proportional to
n
1
/
2
and thus the expected time for it to fire is
O
(1
/n
1
/
2
) for a total expected time
of
O
(1
/n
1
/
2
). Note that power
n
1
/
2
was chosen in the analysis to ensure the optimal tradeoff between the rates of
individual reaction executions and the total number of reaction executions.
4
A reversible reaction
A
+
F
F
′
is simply syntactic sugar for two irreversible reactions
A
+
F
→
F
′
and
F
′
→
A
+
F
.
5
We observe that in the literature on computation in CRNs and population protocols it is almost never the case
that computation is slow because the necessary sequence of reactions is too long – rather, slowdown is dominated by
reaction bottlenecks where two low count species must react. Thus in this work we focus on this essential type of
delay, captured in our notion of speed faults.
3
Our positive result shows how any detection problem can be decided by a speed fault free
CRN, and further shows that this computation is fast in the standard stochastic chemical kinetics
model [12]. The largest part of this paper concerns the negative result that only detection problems
can be computed by speed fault free CRNs (Section 4.2). The proof of the negative result consists
of finding a worst-case reaction sequence that leads to a speed fault, assuming a non-detection
problem is computed.
Absent speed-faults, the
O
(1)-count species must initiate cascades through intermediary large
count species in order to “communicate.” Consider the above “2
A
problem.” We can imagine
isolating the two copies of
A
in “separate test tubes” and then use the symmetry between the two
A
molecules to make the system think that it’s communicating with just one
A
(and thereby fail
to detect the second
A
). To make this argument precise we develop a pumping technique which
formally distinguishes species that can get arbitrarily large with increasing
n
from species whose
counts are bounded by a constant
6
. We show that all large count species that can be encountered
along a trajectory can be pumped to be
simultaneously
large. We then show that in the context
of large counts of all pumpable species, reaction sequences can be decomposed into separate test
tubes (parallel decomposition). A key part of the argument involves showing that the speed fault
free CRN cannot detect small changes to pumpable species; for this we develop a new technique
for performing surgery on reaction sequences.
2 Previous work and future directions
Much related work in the distributed computing community is phrased in the language of population
protocols rather than CRNs (e.g. [2]). While population protocols are equivalent to CRNs with
exactly two reactants and two products, and thus a fixed population size, CRNs can naturally
describe reactions that consume or produce net molecules. As a result CRNs can potentially explore
an unbounded state space, and certain questions that are not natural for population protocols
become germane for CRNs (for example: Turing universality). Because our negative result naturally
applies to a changing population size, we phrase this paper in the language of CRNs.
CRNs have a surprisingly rich computational structure. If we allow the number of species and
reactions to scale with the size of the input (i.e. we view CRNs as a non-uniform model of com-
putation), then log
s
species can deterministically simulate space
s
-bounded Turing machines [6].
(These results are presented in a model called vector addition systems [13], but easily carry over.)
Thus CRNs are a very powerful model of non-uniform computation. On the other hand, we ask
what functions can be computed by a fixed CRN (i.e. fixed number of species and reactions, with
input encoded in the initial molecular counts, which corresponds to a uniform model). In this
setting, CRNs are not Turing universal, unless we allow for some probability of error [3, 16]. In
attempting Turing universal computation, there will provably always be “race conditions” that lead
to error if certain reactions occur in a (maybe unlikely but possible) malicious order. The fact that
even such Turing universal computation is possible, and indeed can be made “fast” is surprising
since finite CRNs necessarily must represent binary data strings in a unary encoding, since they
lack positional information to tell the difference between two molecules of the same species.
Deterministic computation of both predicates and functions has been exactly characterized, and
corresponds to semilinear sets and functions [2, 7]. Angluin, Aspnes, and Eisenstat [2] showed that
all semilinear predicates can be deterministically computed in expected
O
(
n
polylog
n
) “interac-
tions” (molecules bumping into each other). In a volume of fixed size, with
n
molecules, there are
6
Note that our pumping lemma is very different from a similarly called “pumping lemma” of ref. [2], which shows
that how input can be increased without changing the output (thus pumping “input”)
4
an expected Θ(
n
2
) such interactions per unit time, which yields expected time
O
((1
/n
)polylog
n
)
— decreasing with
n
. Our results imply that when computing semilinear predicates other then the
detection problems, it is always possible to reach a state (speed fault) from which the expected
time to finish the computation is Ω(1) — independent of
n
. It is easy to reconcile the two results:
in the construction of ref. [2], the probability that a speed fault is reached decreases with
n
, and
thus the total expected time decreases with
n
as well. Our result implies that this is a necessary
feature of any such construction, and is not simply due to insufficient cleverness of the researchers
to avoid speed faults.
Other work showing the challenges in parallelizing CRNs include the investigation of running
multiple copies of networks in parallel [9], and the inability of networks starting with only large
count species to delay the production of any species [11].
While in this work we focused on parallelizable predicates, it remains to explore the class of
parallelizable functions. For example, if the initial amount of
A
is the input and the final amount
of
B
is the output, then we can think of the reaction
F
+
A
→
2
B
as deterministically computing
f
(
x
) = 2
x
. Clearly as the amount of
F
increases, the computation converges faster. On the other
hand, we believe that computing division by 2 should not be possible without speed faults, although
that remains to be shown.
Since the occurrence of a speed fault leads to a slow computational bottleneck, speed faults
affect the tail bounds on the distribution of the computation time. Indeed, two CRNs may compute
with the same fast expected time, but the one susceptible to speed faults will likely have a larger
probability of taking significantly longer. It remains to rigorously draw out the connection between
tail bounds and speed faults.
3 Preliminaries
3.1 Chemical reaction networks
If Λ is a finite set (in this paper, of chemical species), we write
N
Λ
to denote the set of functions
f
: Λ
→
N
. Equivalently, we view an element
c
∈
N
Λ
as a vector of
|
Λ
|
nonnegative integers, with
each coordinate “labeled” by an element of Λ. Given
S
∈
Λ and
c
∈
N
Λ
, we refer to
c
(
S
) as the
count of
S
in
c
. Let
|
c
|
=
‖
c
‖
∞
= max
S
∈
Λ
c
(
S
). We write
c
≤
c
′
to denote that
c
(
S
)
≤
c
′
(
S
) for
all
S
∈
Λ, and
c
<
c
′
if
c
≤
c
′
and
c
6
=
c
′
. Since we view vectors
c
∈
N
Λ
equivalently as multisets
of elements from Λ, if
c
≤
c
′
we say
c
is a
subset
of
c
′
. Given
c
,
c
′
∈
N
Λ
, we define the vector
component-wise operations of addition
c
+
c
′
, subtraction
c
−
c
′
, and scalar multiplication
n
c
for
n
∈
N
. For a set ∆
⊂
Λ, we view a vector
c
∈
N
∆
equivalently as a vector
c
∈
N
Λ
by assuming
c
(
S
) = 0 for all
S
∈
Λ
\
∆
.
Write
c
∆ to denote the vector
d
∈
N
∆
such that
c
(
S
) =
d
(
S
) for all
S
∈
∆. Given
S
1
,...,S
k
∈
Λ,
c
∈
N
Λ
, and
n
1
,...,n
k
∈
Z
,we write
c
+
{
n
1
S
1
,...,n
k
S
k
}
to denote
vector addition of
c
with the vector
v
∈
Z
{
S
1
,...,S
k
}
with
v
(
S
i
) =
n
i
.
Given a finite set of chemical species Λ, a
reaction
over Λ is a triple
α
=
〈
r
,
p
,k
〉∈
N
Λ
×
N
Λ
×
R
+
,
specifying the stoichiometry (amount consumed/produced) of the reactants and products, respec-
tively, and the
rate constant
k
. A reaction is
unimolecular
if it has one reactant and
bimolecular
if
it has two reactants. We use no higher-order reactions in this paper. For simplicity, in this paper
we use
k
= 1 and the rate constant is omitted. For instance, given Λ =
{
A,B,C
}
, the reaction
A
+ 2
B
→
A
+ 3
C
is the pair
〈
(1
,
2
,
0)
,
(1
,
0
,
3)
〉
.
A
(finite) chemical reaction network (CRN)
is a
pair
N
= (Λ
,R
), where Λ is a finite set of chemical
species
, and
R
is a finite set of reactions over
Λ. A
state
of a CRN
N
= (Λ
,R
) is a vector
c
∈
N
Λ
.
Given a state
c
and reaction
α
=
〈
r
,
p
〉
, we say that
α
is
applicable
to
c
if
r
≤
c
(i.e.,
c
contains
enough of each of the reactants for the reaction to occur). If
α
is applicable to
c
, then write
α
(
c
)
5
to denote the state
c
+
p
−
r
(i.e., the state that results from applying reaction
α
to
c
). A finite or
infinite sequence of reactions (
α
i
), where each
α
i
∈
R
, is a
reaction sequence
. Given an initial state
c
0
and a reaction sequence (
α
i
), the induced
execution sequence
(or
path
)
q
is a finite or infinite
sequence of states
q
= (
c
0
,
c
1
,
c
2
,...
) such that, for all
c
i
∈
q
(
i
≥
1),
c
i
=
α
i
(
c
i
−
1
).
7
If a finite
execution sequence
q
starts with
c
and ends with
c
′
, we write
c
=
⇒
q
c
′
. We write
c
=
⇒
c
′
if such
an execution sequence exists and we say that
c
′
is
reachable
from
c
.
3.2 Abstract algebra
A few concepts from abstract algebra have proven useful in describing the reachable states of
CRNs, as well as characterizing their computational power (see Section 3.3).
A set
A
⊆
N
k
is
linear
if
A
=
{
b
+
∑
p
i
=1
n
i
u
i
|
n
1
,...,n
p
∈
N
}
for some constant vectors
b
,
u
1
,...,
u
p
∈
N
k
.
A
is
semilinear
if it is a finite union of linear sets.
A
is a
monoid
if
0
∈
A
and
A
+
A
⊆
A
, i.e.,
A
is
closed under addition. We say that
A
is a
monoid coset (a.k.a. monoid offset)
if
A
=
b
+
M
for
some constant vector
b
∈
N
k
and monoid
M
⊆
N
k
.
A powerful result due to Leroux helps to restrict the complexity of the set of reachable states.
(Leroux actually proves a more powerful result involving the first-order definability of certain sets,
but the following implication is sufficient for our purposes.) For any CRN
N
= (Λ
,R
) and set
X
⊆
N
Λ
, let post
N
(
X
) =
{
y
∈
N
Λ
∣
∣
(
∃
x
∈
X
)
x
=
⇒
N
y
}
be the set of states reachable from
some state in
X
.
Theorem 3.1
( [14])
.
If
X
⊆
N
Λ
is semilinear, then
post
N
(
X
)
is a finite union of monoid cosets.
We will find ourselves frequently dealing with infinite sequences of states. The following techni-
cal lemma elucidates certain convenient properties of any such sequence and will be used repeatedly.
Lemma 3.2
(Dickson’s Lemma [10])
.
The set of states
N
k
is well-quasi-ordered. In particular,
every infinite sequence
x
0
,
x
1
,...
of states has an infinite nondecreasing subsequence
x
i
0
≤
x
i
1
≤
...
,
where
i
0
< i
1
< ...
∈
N
, and every set
U
⊆
N
k
has a finite number of minimal elements.
3.3 Stable decidability of predicates
We now review the definition of stable decidability of predicates introduced by Angluin, Aspnes,
and Eisenstat [2]. Intuitively, some species “vote” for a YES/NO answer, and a CRN
N
is a stable
decider if
N
is guaranteed to reach a consensus vote.
A
chemical reaction decider
(CRD) is a tuple
D
= (Λ
,R,
Σ
,
Υ
,φ,
s
), where (Λ
,R
) is a CRN,
Σ
⊆
Λ is the
set of input species
, Υ
⊆
Λ is the set of
voters
,
φ
: Υ
→ {
NO
,
YES
}
is the
(Boolean)
output function
, and
s
∈
N
Λ
\
Σ
is the
initial context
. For the input vector (
n
1
,...,n
k
)
∈
N
k
, where
k
=
|
Σ
|
, we write the initial state as
i
(
n
1
,...,n
k
)
∈
N
Λ
defined by:
i
(
n
1
,...,n
k
)
Σ = (
n
1
,...,n
k
)
and
i
(
n
1
,...,n
k
)
(Λ
\
Σ) =
s
.
We extend
φ
to a partial function on states Ψ :
N
Λ
99K
{
NO
,
YES
}
as follows. Ψ(
c
) is undefined if either
c
(
X
) = 0 for all
X
∈
Υ, or if there exist
X
0
,X
1
∈
Υ such that
c
(
X
0
)
>
0,
c
(
X
1
)
>
0,
φ
(
X
0
) =
NO
and
φ
(
X
1
) =
Y ES
. Otherwise, there exists
b
∈ {
NO,Y ES
}
such that (
∀
X
∈
Υ)(
c
(
X
)
>
0 implies
φ
(
X
) =
b
); in this case, the
output
Ψ(
c
) of state
c
is
b
.
A state
o
is
output stable
if Ψ(
o
) is defined and, for all
c
such that
o
=
⇒
c
, Ψ(
c
) = Ψ(
o
). We
call a whole CRD
D
stable
if, for any initial state
i
, there exists
b
∈{
NO,Y ES
}
such that, for every
state
x
reachable from
i
, there is an output stable state
o
reachable from
x
such that Ψ(
o
) =
b
7
When the initial state to which a reaction sequence is applied is clear from context, we may overload terminology
and refer to a reaction sequence and an execution sequence interchangeably. The possiblity that different reactions
could result in identical state change (e.g.,
A
→
B
and
A
+
C
→
B
+
C
when
C
is present) is immaterial to the
arguments in this paper.
6
(i.e.,
D
always converges to a defined output
b
on input
i
, where
b
depends only on
i
and not on
the path taken). If
D
is stable, then for some unique subset
S
0
⊆
N
k
of inputs it always converges
to output 0 and stays with that output, and for the remainder
S
1
=
N
k
\
S
0
it always converges
to output 1 and stays with that output. We say that
D
stably decides
the set
S
1
, or that
D
stably
decides
the predicate
ψ
:
N
k
→{
0
,
1
}
defined by
ψ
(
x
) = 1 iff
x
∈
S
1
.
A set
A
⊆
N
k
is
linear
if
A
=
{
b
+
∑
p
i
=1
n
i
u
i
|
n
1
,...,n
p
∈
N
}
for some constant vectors
b
,
u
1
,...,
u
p
∈
N
k
.
A
is
semilinear
if it is a finite union of linear sets. The following theorem is
due to Angluin, Aspnes, and Eisenstat [2]:
Theorem 3.3
( [2])
.
A set
A
⊆
N
k
is stably decidable by a CRD if and only if it is semilinear.
If a YES voter (or any other species, for that matter) cannot be produced by any sequence
of reactions from a state
y
, then it cannot be produced from any subset
y
′
≤
y
.
The following
lemma is useful when we want to argue the other way: that for certain species, beyond a certain
value,
increasing
their counts cannot affect the ability or inability of the state to produce a YES
voter. We say that a state
c
is
committed
if, for all states
z
such that
c
=
⇒
z
,
z
(
S
) = 0 for all
YES-voting species
S
. In particular, all output-stable NO states are committed, and for stable
CRDs, committed states are reachable only from inputs on which the predicate is false.
8
Lemma 3.4.
For each CRD, there is a constant
c
such that, for all committed states
c
, if
c
(
S
)
> c
for some
S
∈
Λ
, then for all
n
∈
Z
,
c
+
{
nS
}
is also committed.
Proof.
The negation of a state
u
being committed is that there exists a (possibly empty) sequence
of reactions
r
such that
u
=
⇒
r
z
and there is a YES-voting species
Y
with
z
(
Y
)
>
0. Call such a
state
uncommitted
, and let
U
be the set of all uncommitted states. Note that
U
is “upward closed”:
if
u
∈
U
, then all
v
≥
u
are also uncommitted since
r
can be applied to
v
as well. Hence it is clear
that if
n
≤
0,
c
+
{
nS
}
is committed, since
c
+
{
nS
}≤
c
.
By Dickson’s Lemma, every set
U
⊆
N
Λ
has a finite number of minimal elements, i.e. vectors
m
∈
U
such that, for all
u
∈
U
,
u
≤
m
implies
u
=
m
. Call this set of minimal elements
M
.
Suppose for the sake of contradiction that (
∃
u
∈
U
)(
∀
m
∈
M
)
m
6≤
u
. Then
u
is minimal, hence
u
∈
M
, but
u
≤
u
, which contradicts our supposition.
Thus (
∀
u
∈
U
)(
∃
m
∈
M
)
m
≤
u
. Because
U
is upward closed, we conclude that
U
=
⋃
m
∈
M
{
u
|
u
≥
m
}
, i.e.,
U
is a finite union of “cones”. The lemma follows by choosing
c
=
max
m
∈
M,S
∈
Λ
m
(
S
).
4 Speed fault free CRDs
In this section we show our main result that speed fault free CRDs decide only “detection problems,”
i.e., detecting the presence or absence of a species, but not distinguishing between two different
positive counts of it. To allow for “parallelization” of the computation, we introduce a “fuel”
species
F
, whose count is allowed to start arbitrarily large.
9
Increasing the amount of fuel species
is analogous to increasing the amount of “receptor” in the introduction. We then formalize the
concept of “speed fault free” discussed informally in the introduction. Briefly, a CRN experiences a
8
A committed state is not be output-stable NO if a state without any voters is reachable from it. The distinct
notion of “committed” is useful because (unlike for output NO stability) the negation of committed is closed under
superset (see the proof of Lemma 3.4), yet (like for output NO stability) reaching a committed state implies that the
predicate value must be false.
9
Allowing multiple fuel species
F
1
, F
2
, . . .
does affect our results since one of our reactions can be
F
→
F
1
+
F
2
. . .
.
7
speed fault if it reaches a state from which all paths to a correct state execute some reaction when
the counts of all of its reactants are bounded by a constant (a “slow” reaction). Note that in the
stochastic model, the expected time for such a reaction to occur is bounded below by a constant
(independent of the amount of fuel).
Let
D
= (Λ
,R,
Σ
,
Υ
,φ,
s
) be a stable CRD, where Σ =
{
A
1
,...,A
k
}
are the input species and
Λ
\
Σ contains a special “fuel” species
F
, with variable initial count
n
. The initial count of every
other species in Λ
\
(Σ
∪{
F
}
) is
s
(unchanging with respect to
n
). Write the initial state of
D
with
some number
n
i
of each input
A
i
and
n
molecules of
F
as
i
n
(
n
1
,...,n
k
).
Let
f
∈
N
, let
α
∈
R
be a reaction and
x
∈
N
Λ
be a state. We say that
α
occurring in state
x
is
f
-fast
if at least one reactant has count at least
f
in
x
. An execution sequence is called
f
-
fast
if
all reactions in it are
f
-fast.
10
Definition 4.1.
A stable CRD
D
is
speed fault free
if for all
n
1
,...,n
k
and all
f
∈
N
, for all
sufficiently large
n
,
11
for any state
x
such that
i
n
(
n
1
,...,n
k
) =
⇒
x
, there is an output stable state
y
(which has the correct answer with respect to
n
1
,...,n
k
by the stability of
D
) such that
x
=
⇒
y
by an
f
-fast execution sequence.
In other words, from any reachable state (whether reachable by a fast or slow sequence of
reactions), there is always a sequence of fast reactions that reaches the correct answer.
Definition 4.2.
A set
S
⊆
N
k
is a
simple detection set
if there is a 1
≤
i
≤
k
such that
S
=
{
(
x
1
,...,x
k
)
∈
N
k
∣
∣
x
i
>
0
}
.
A set is a
detection set
if it is expressible as a combination of finite
unions, intersections, and complements of simple detection sets.
In other words, the predicate corresponding to a simple detection set
S
is a finite Boolean
combination of questions of the form “is a certain species present?”. The following theorem is
the main result of this paper. We show each direction in two separate lemmas, Lemma 4.4 and
Lemma 4.13.
Theorem 4.3.
The sets decidable by speed fault free CRDs are precisely the detection sets.
4.1 Detection problems are decidable by speed fault free CRDs
Since we argue that the CRD is fast under the standard stochastic time model [12] in addition to
being speed fault free, we must first define this model. Since all rate constants in this paper are 1,
we define time assuming this to be true.
Given a fixed volume
v
and current state
c
, the
propensity
of a unimolecular reaction
α
:
X
→
...
in state
c
is
ρ
(
c
,α
) =
c
(
X
). The propensity of a bimolecular reaction
α
:
X
+
Y
→
...
, where
X
6
=
Y
, is
ρ
(
c
,α
) =
c
(
X
)
c
(
Y
)
v
. The propensity of a bimolecular reaction
α
:
X
+
X
→
...
is
ρ
(
c
,α
) =
1
2
c
(
X
)(
c
(
X
)
−
1)
v
. The propensity function determines the kinetics of the system as follows. The time
until the next reaction occurs is an exponential random variable with rate
ρ
(
c
) =
∑
α
∈
R
ρ
(
c
,α
).
The probability that next reaction will be a particular
α
next
is
ρ
(
c
,α
next
)
ρ
(
c
)
.
The kinetic model is based on the physical assumption of well-mixedness valid in a dilute
solution. Thus, we assume the
finite density constraint
, which stipulates that the volume to execute
a CRN must be proportional to the maximum molecular count obtained during execution [16].
10
It is worth noting that fast reaction sequences are not necessarily fast in the standard sense of stochastic kinetics,
since although each reaction occurs quickly, it could be that there are a huge number of reactions in the sequence.
Since our main result is a lower bound, this does not hurt the argument (and our upper bound result also shows that
it is possible to decide detection problems quickly under the standard stochastic model).
11
n
may need to be larger for different input values
n
1
, . . . , n
k
and different constants
f
.
8
Lemma 4.4.
Every detection set is decidable by a speed fault free CRD. This CRD takes expected
time
O
(log
n/n
)
expected time to stabilize under the standard model of stochastic chemical kinetics
with constant volume.
Proof.
We describe the CRD using the language of “agent states” from population protocols. By
this we mean that for each “agent”
F
with
l
different states, there are species
F
1
,...,F
l
, and an
agent “changing state” from
i
to
j
upon reacting with a molecule
X
means that we have a reaction
of the form
X
+
F
i
→
F
j
+
...
.
Let
A
1
,...,A
k
the input species of the detection problem.
F
has 2
k
states to keep track of the
k
bits “is
A
i
present?” for each 1
≤
i
≤
k
, so that each fuel species is written
F
b
1
...b
k
where each
b
i
∈{
0
i
,
1
i
}
, and the initial state of all
n F
’s is
F
0
1
...
0
k
. For each
F
b
1
...
0
i
...b
k
, we have the reactions
F
b
1
...
0
i
...b
k
+
A
i
→
F
b
1
...
1
i
...b
k
+
A
i
F
b
1
...
0
i
...b
k
+
F
b
1
...
1
i
...b
k
→
2
F
b
1
...
1
i
...b
k
First we argue that the expected time to converge to an answer is
O
(log
n
). Each
F
species votes
in accordance with the detection problem, according to whether its state indicates the answer is
yes or no. We start with
n
copies of
F
and at most
O
(1) copies of each
A
i
.
12
In expected time
log
k
=
O
(1) with respect to
n
(since
k
is a constant depending on the detection problem but not on
n
), each
A
i
species with positive count has encountered at least one
F
molecule. It takes
O
(log
n
)
expected time for a single bit to propagate to the entire population of
F
’s. Therefore it takes at
most
kO
(log
n
) =
O
(log
n
) (again, since
k
is a constant independent of
n
) for all bits to propagate.
At this point all fuel agents have the same state, so they all vote unanimously and correctly.
Now we argue that the CRD is speed fault free. Let
x
be any reachable state, and let
A
i
be a
species with
x
(
A
i
)
>
0 that has not yet reacted with any fuel. Then all
n
fuel molecules have bit
b
i
= 0
i
, so for at least one assignment to the other
k
−
1 bits, some fuel species has count at least
n
2
k
−
1
, so the first reaction above with that fuel species is
n
2
k
−
1
-fast. Suppose that
x
(
A
i
)
>
0 but has
reacted with at least one fuel. Then the second reaction, executed at most
n
times, will stabilize
the value of bit
b
i
to be 1
i
. Since the number of fuel molecules with bit 0
i
plus the number with bit
1
i
is exactly
n
, by a similar argument, there must be some assignment to all
k
bits such that a fuel
species with that assignment has count at least
n
2
k
, whence the second reaction with that species is
n
2
k
-fast. Therefore there is always a
n
2
k
-fast path to an output-stable state with the correct answer,
which occurs when all bits
b
i
corresponding to positive-count species
A
i
become 1
i
, implying that
the CRD is speed fault free.
4.2 Speed fault free CRDs decide only detection problems
Before proceeding to the main argument, we need to develop some technical machinery. We first
show that if a fast execution sequence is used to decrease the count of some species, then we can
identify certain reactions that must necessarily occur (reaction extraction). We then develop a
notion of pumping, which is used to identify species that can get arbitrarily large with increasing
fuel. Finally, we show that reaction sequences in which one reactant is always pumpable can be
decomposed into separate “test-tubes” (parallel decomposition). Finally we stitch these notions
together to show that speed fault free CRDs cannot compute more than detection problems.
12
So that the total volume required is
O
(
n
), although the initial count of
A
i
maybe be larger than
n
, we measure
time asymptotically with respect to increasing
n
, so we consider the initial count of
A
i
to be constant with respect
to
n
. With some care we could handle cases when the count of the
A
’s is much larger than
n
, simply by having all
A
molecules act like fuels as well, but since this complicates the exposition without changing the basic proof idea, we
keep the presentation simply by assuming
n
= Ω(#
0
A
i
) for each
i
.
9
4.2.1 Reaction extraction lemma
The following lemma is a key technical tool used in our proof of the main result. Intuitively, the
lemma below states that a fast reaction sequence that decreases certain species from high counts
to low counts must contain reactions of a certain restricted form. These reactions will later be
used to do “surgery” on fast reaction sequences, because they give a way to alter the count of
certain species, by inserting or removing those reactions, while carefully controlling the effect these
insertions and removals have on counts of other species.
Lemma 4.5.
Let
c
1
,c
2
∈
N
such that
c
2
>
|
Λ
|·
c
1
, let
x
,
y
∈
N
Λ
such that
x
=
⇒
y
via
c
2
-fast reaction
sequence
q
. Define
∆ =
{
D
∈
Λ
|
x
(
D
)
≥
c
2
and
y
(
D
)
≤
c
1
}
.
Then there is an order on
∆
, so
that we may write
∆ =
{
D
1
,D
2
,...,D
l
}
, such that, for all
i
∈{
1
,...,l
}
, there is a reaction
α
i
of
the form
D
i
→
P
1
+
...
+
P
k
or
D
i
+
S
→
P
1
+
...
+
P
k
, such that
S,P
1
,...,P
k
6∈ {
D
1
,...,D
i
}
,
and
α
i
occurs at least
c
2
−|
Λ
|·
c
1
|
R
|
times in
q
in states
c
in which
c
(
S
)
≥
c
2
.
Proof.
We define the ordering based on increasing sets
∅
= ∆
0
⊂
∆
1
⊂
∆
2
⊂
...
∆
l
−
1
⊂
∆
l
= ∆,
where for each 1
≤
i
≤
l
, ∆
i
\
∆
i
−
1
=
{
D
i
}
.
We define the ordering inductively “in reverse,” by first defining
D
l
, then
D
l
−
1
, etc. For all
1
≤
i
≤
l
, define Φ
i
:
N
Λ
→
N
for all states
c
by Φ
i
(
c
) =
∑
D
∈
∆
i
c
(
D
). Φ
l
is well-defined since
∆
l
= ∆, and Φ
i
is well-defined once we have defined
D
i
+1
,...,D
l
, because ∆
i
= ∆
\{
D
i
+1
,...,D
l
}
.
Because
y
(
D
)
≤
c
1
for all
D
∈
∆, it follows that Φ
i
(
y
)
≤
i
·
c
1
≤|
Λ
|·
c
1
. Recall that
x
(
D
)
≥
c
2
for all
D
∈
∆. Let
r
be the suffix of
q
after the last state
c
′
along
q
such that Φ
i
(
c
′
)
≥
c
2
. Then
in all states
c
in
r
(not including
c
′
itself),
c
(
D
)
< c
2
for all
D
∈
∆
i
. Because Φ
i
(
c
′
)
≥
c
2
,
r
must
contain a subsequence
s
of reactions, each of which strictly decreases Φ
i
, and the total decrease in
Φ
i
over all of
s
is at least (
c
2
−|
Λ
|·
c
1
) between states
c
′
and
y
.
Since all reactions in
s
strictly decrease Φ
i
, all reactions must have a reactant in ∆
i
. Since
s
is
c
2
-fast, and all states
c
along
s
have
c
(
D
)
< c
2
for
D
∈
∆
i
, the reaction cannot be unimolecular
since the count of
D
is too low for the reaction to be
c
2
-fast, so the reaction must be bimolecular
with the other reactant
S
having count at least
c
2
. This implies
S
6∈
∆
i
(since all
D
∈
∆
i
have count
< c
2
between
c
′
and
y
). For the reaction to strictly decrease Φ
i
, all products
P
6∈
∆
i
(otherwise Φ
i
would either stay equal or increase after applying the reaction). In fact, this implies every reaction
in
s
decreases Φ
i
by exactly 1. Since there are at least
c
2
−|
Λ
|·
c
1
instances of such reactions in
s
,
and there are at most
|
R
|
total types of reactions, by the pigeonhole principle at least one reaction
type must repeat in
s
at least
c
2
−|
Λ
|·
c
1
|
R
|
times.
4.2.2 Pumpable sets of species
This section defines
pumpable
sets of species: species whose counts can be made arbitrarily large by
increasing the amount of fuel (species
F
, see Definition 4.1) and proves some basic properties about
them. For example, the fuel species
F
is trivially pumpable. If there is a reaction
F
+
A
→
F
′
+
A
,
then
F
′
is pumpable (if there is an
A
), because
F
can be arbitrarily large. To get a handle on
the notion of speed fault free, we define pumping to enforce a certain kind of self-consistency
(Π-friendly): you can pump without requiring any reactions where all reactants are not pumpable.
Let Π
⊆
Λ. If a reaction has at least one reactant in Π, say the reaction is Π
-friendly
. If
x
=
⇒
y
via a reaction sequence in which all reactions are Π-friendly, then we write
x
=
⇒
Π
y
. Let
Z
= (
z
1
≤
z
2
≤
z
3
...
), where each
z
n
∈
N
Λ
, be an infinite nondecreasing sequence of states. A
set of species Π
⊆
Λ is
Z
-pumpable
if there exists a sequence of states
X
= (
x
1
,
x
2
,...
) such that:
(1) for all
P
∈
Π and
m
∈
N
,
x
m
(
P
)
≥
m
, and (2) for all
m
∈
N
, there exists
n
∈
N
such that
10
z
n
=
⇒
Π
x
m
.
13
Call such a sequence (
x
m
) a
pumping sequence
for Π. Π is
maximal
Z
-pumpable
if
it is
Z
-pumpable and no strict superset of Π is
Z
-pumpable.
The next proposition shows that after pumping a maximal Π, all other species have bounded
counts in all states reachable by Π-friendly paths.
Proposition 4.6.
Let
Z
= (
z
1
≤
z
2
≤
...
)
be a infinite nondecreasing sequence of states, and let
Π
⊆
Λ
be maximal
Z
-pumpable, with pumping sequence
(
x
m
)
. Then there is a constant
c
such that,
for all states
y
and
m,n
∈
N
such that
x
m
=
⇒
Π
y
, then for all
S
∈
Λ
\
Π
,
y
(
S
)
< c
.
Proof.
Suppose otherwise. There exists
S
∈
Λ
\
Π and an infinite number of
m
∈
N
such that
x
m
=
⇒
Π
r
m
y
m
and
y
m
(
S
)
≥
k
m
, where
k
m
increases without bound as
m
→ ∞
. By Dickson’s
Lemma we can assume each
x
m
<
x
m
+1
, so that
r
m
is applicable to
x
m
′
for all
m
′
> m
. Then by
choosing
m
′
sufficiently large,
x
m
′
=
⇒
Π
r
m
y
m
′
, where
y
m
′
(
S
)
≥
m
and for all
X
∈
Π,
y
m
′
(
X
)
≥
m
′
,
showing that Π
∪{
S
}
is
Z
-pumpable and contradicting the maximality of Π.
We will use Proposition 4.6 repeatedly, but its most important consequence, intuitively, is that
that the only way to get something outside of Π “large” is by executing a “slow” reaction (between
two reactants not in Π). This is captured by the following corollary.
Corollary 4.7.
Let
Z
= (
z
1
≤
z
2
≤
...
)
be a infinite nondecreasing sequence of states, and
let
Π
⊆
Λ
be maximal
Z
-pumpable, with pumping sequence
(
x
m
)
. Let
c
∈
N
be the constant in
Proposition 4.6 ensuring that in any state
c
such that
x
m
=
⇒
Π
c
,
c
(
S
)
< c
for all
S
∈
Λ
\
Π
. Then
if
x
m
=
⇒
p
c
′
and
c
′
(
S
)
≥
c
, where
S
∈
Λ
\
Π
, some reaction in
p
is not
c
-fast.
Proof.
Proposition 4.6 ensures that if
p
is Π-friendly, then no such
S
∈
Λ
\
Π exists. Therefore
p
is not Π-friendly. Let
α
be the first reaction along
p
that is not Π-friendly. Since the state
immediately preceding this reaction is reachable by a Π-friendly path, Proposition 4.6 tells us that
all species
S
∈
Λ
\
Π have count less than
c
. Therefore
α
occurs when the count of all its reactants
is less than
c
, hence it is not
c
-fast.
Proposition 4.8.
Let
Z
= (
z
1
≤
z
2
≤
...
)
be a infinite nondecreasing sequence of states, and let
Π
⊆
Λ
be maximal
Z
-pumpable. If
R
contains a reaction with all reactants in
Π
, then all products
are in
Π
.
Proof.
For each
m
∈
N
, let
x
m
be reachable from some
z
n
such that
x
m
(
S
)
≥
m
for all
S
∈
Π.
If
X
6
=
Y
, then from state
x
m
execute the reaction
X
+
Y
→
... m/
2 times. This results in a
state in which all products of the reaction, as well as
X
and
Y
, have count at least
m/
2, and all
other species in Π besides
X
and
Y
have count at least
m > m/
2. Since
m/
2 grows unboundedly,
this establishes that the products are maximal
Z
-pumpable as well. If
X
=
Y
, then execute the
reaction
m/
3 times, which ensures that the counts of
X
,
Y
, and all products are at least
m/
3,
similarly establishing that the products are pumpable.
4.2.3 Parallel decomposition
Intuitively, the following lemma shows that systems reacting by Π-friendly reactions can be effec-
tively decomposed into separate non-interacting “test tubes” (in the context of a large excess of
Π).
14
13
We can assume that
n
→∞
as
m
→∞
. This is because (
z
n
) is a nondecreasing sequence, and so if
z
n
=
⇒
Π
x
m
for some
n, m
∈
N
, then for all
n
′
> n
, there is a superset
x
′
m
≥
x
m
such that
z
n
′
=
⇒
Π
x
′
m
, and
x
′
m
(
S
)
≥
m
for all
S
∈
Π.
14
Note that in this way Π-friendly bimolecular reactions act somewhat analogously to unimolecular reactions: if
x
+
y
=
⇒
z
by a sequence of unimolecular reactions, then
x
=
⇒
z
′
and
y
=
⇒
z
′′
such that
z
′
+
z
′′
=
z
.
11
For a reaction sequence
q
applied to a state
x
to give
x
=
⇒
q
y
, where
x
is written as a sum of
two states
x
1
+
x
2
=
x
, we say that
q
has a
parallel decomposition from
(
x
1
,
x
2
) if there exists a
partition of
q
into two disjoint subsequences of reactions (
q
1
,q
2
) such that
x
1
=
⇒
q
1
y
1
,
x
2
=
⇒
q
2
y
2
,
and
y
=
y
1
+
y
2
. In other words, if we imagine splitting
x
into two “tubes”
x
1
and
x
2
, then the
evolution determined by the reaction sequence
q
can be interpreted as happening entirely within
the tubes.
Suppose a reaction sequence
p
is applicable to
x
=
x
1
+
x
2
, but
p
does not have a parallel
decomposition from (
x
1
,
x
2
). Then there is a longest prefix
q
of
p
(possibly
q
is empty) such that
q
has a parallel decomposition (
q
1
,q
2
) from (
x
1
,
x
2
), then we call
q
the
join
of
p
from (
x
1
,
x
2
).
Write (
x
′
1
,
x
′
2
) to be such that
x
1
=
⇒
q
1
x
′
1
and
x
2
=
⇒
q
2
x
′
2
.
In other words,
q
is the furthest that
x
1
and
x
2
can evolve on their own before the next reaction in
p
requires a molecule from
x
′
1
and a
molecule from the other
x
′
2
. Therefore the next reaction must be bimolecular
X
1
+
X
2
→
...
, and
it must be the case that
x
′
1
(
X
2
) = 0 and
x
′
2
(
X
1
) = 0, otherwise one of the reaction sequences
q
1
or
q
2
could be extended by that reaction while remaining a parallel decomposition, and
q
would not
be the longest prefix of
p
with a parallel decomposition.
Lemma 4.9.
Suppose
x
+
y
=
⇒
Π
z
. Then there are
p
,
p
′
,
p
′′
∈
N
Π
, and
z
′
,
z
′′
∈
N
Λ
such that
p
+
x
=
⇒
Π
p
′
+
z
′
and
p
+
y
=
⇒
Π
p
′′
+
z
′′
, where
z
′
+
z
′′
=
z
and
p
′
+
p
′′
= 2
p
.
Proof.
Let
p
be the Π-friendly reaction sequence
x
+
y
=
⇒
z
. Let
p
n
∈
N
Π
consist of exactly
n
molecules of every species in Π. For any
p
n
, consider the path: 2
p
n
+
x
+
y
=
⇒
p
2
p
n
+
z
. Let
q
n
be the join of
p
from (
p
n
+
x
,
p
n
+
y
) and let (
r
n
,l
n
) be the parallel decomposition of
q
from
(
p
n
+
x
,
p
n
+
y
). Let
l
n
and
r
n
be such that
p
n
+
x
=
⇒
r
n
l
n
and
p
n
+
y
=
⇒
l
n
r
n
. If
q
n
=
p
then
we are done:
p
n
+
x
=
⇒
l
n
by a Π-friendly reaction sequence and
p
n
+
y
=
⇒
r
n
by a Π-friendly
reaction sequence where
l
n
+
r
n
=
z
+ 2
p
. Otherwise,
q
n
is not all of
p
. The next reaction in
p
after
q
n
must be of the form
L
+
R
→
...
where, without loss of generality,
l
n
(
R
) = 0,
l
n
(
L
)
>
0
and
r
n
(
L
) = 0,
r
n
(
R
)
>
0. Since
p
is Π-friendly, at least one reactant
L
or
R
is in Π. Now consider
q
n
+1
, the join of
p
from (
p
n
+1
+
x
,
p
n
+1
+
y
).
q
n
+1
must be longer by at least 1 reaction by the
following argument. If
L
∈
Π then
r
n
+1
(
L
) = 1, and if
R
∈
Π then
l
n
+1
(
L
) = 1. Since we still have
r
n
+1
(
R
)
>
0 and
l
n
+1
(
L
)
>
0, the above reaction from
p
can occur in either
l
n
+1
or
r
n
+1
. Since
p
is finite, at some point
q
=
p
and we are done.
4.2.4 Main proof
Throughout this section, let
D
= (Λ
,R,
Σ
,
Υ
,φ,
s
) be an arbitrary speed fault free CRD with
Σ =
{
A
1
,...,A
k
}
and fuel species
F
as in Definition 4.1. Supposing for the sake of contradiction
that
D
decides some non-detection set, then there must exist some species
A
i
(assume without loss
of generality that
i
= 1), and an input value (
n
1
,n
2
,...,n
k
)
∈
N
k
, where
n
1
≥
1, with answer NO
(without loss of generality) but input value (
n
1
+ 1
,n
2
,...,n
k
) with answer YES.
For each
n
∈
N
, write the initial state of
D
with answer NO and
n
fuels as
i
n
(=
{
n
1
A
1
, n
2
A
2
,
..., n
k
A
k
, nF,
s
(Λ
\
(Σ
∪{
F
}
))
}
). Our argument will focus on the initial state
i
n
with answer
NO, for sufficiently large
n
, and
i
n
with one extra copy of
A
1
, which has answer YES. We will show
that for sufficiently large
n
,
i
n
+
{
A
1
}
is able to reach a state without YES-voting species, from
which the only way to produce a YES voter is to execute a slow bimolecular reaction.
Let
I
= (
i
1
,
i
2
,...
) be the infinite increasing sequence of all such initial states with intended
answer NO.
We first observe that for a maximal
I
-pumpable set Π, due to Theorem 3.1, there is a very
controlled manner in which the species in Π can be pumped.
12
Lemma 4.10.
Let
Π
be maximal
I
-pumpable. There exists
d
∈
N
Λ
, with
d
(
S
)
>
0
⇐⇒
S
∈
Π
,
and an infinite sequence of states
x
1
,
x
2
,...
such that, for all
m
∈
Z
+
,
x
m
+
d
=
x
m
+1
, and there
exists
n
∈
N
such that
i
n
=
⇒
Π
x
m
.
Proof.
For each
m
∈
N
, let
x
′
m
be reachable via Π-friendly reactions from some
i
n
such that
x
′
m
(
S
)
≥
m
for all
S
∈
Π. Note that
I
is semilinear (in fact linear). Remove all reactions from our
original CRN that are not Π-friendly to obtain a new CRN
N
Π
. We then apply Theorem 3.1 to the
new CRN
N
Π
to obtain the following. There exists
b
1
,...,
b
l
∈
N
Λ
and monoids
M
1
,...,M
l
⊆
N
Λ
such that post
N
Π
(
I
) =
⋃
l
j
=1
(
b
j
+
M
j
). Let
n >
max
1
≤
j
≤
l,S
∈
Λ
b
j
(
S
). Since
x
′
n
∈
post
N
Π
(
I
), there is a
j
such that
x
′
n
∈
b
j
+
M
j
.
Let
d
=
x
′
n
−
b
i
. Define
x
1
=
x
′
n
, and for all
m
∈
Z
+
, define
x
m
+1
=
x
m
+
d
. Note that each
x
m
∈
b
j
+
M
j
since
M
i
is closed under addition, so
x
m
is reachable from sufficiently large
i
n
. Since
x
′
n
(
S
)
>
b
j
(
S
) for all
S
∈
Π,
d
(
S
) =
x
′
n
(
S
)
−
b
j
(
S
)
>
0. The fact that
d
(
S
)
>
0 =
⇒
S
∈
Π
follows from the maximality of Π: any species
S
for which
d
(
S
)
>
0 satisfies
x
m
(
S
)
≥
m
, which
implies that
S
∈
Π.
Define the sequence of output-stable NO states (
y
m
) inductively as follows. For the base case,
let
y
1
be any output-stable NO state such that
x
1
=
⇒
r
1
y
1
; such a path
r
1
must exist because
D
is stable. Inductively assume that
x
m
−
1
=
⇒
r
m
−
1
y
m
−
1
. Then
x
m
=
x
m
−
1
+
d
=
⇒
r
m
−
1
y
m
−
1
+
d
.
Let
f
m
∈
N
be the largest number such that there is a
f
m
-fast path
p
m
from
y
m
−
1
+
d
to an
output-stable NO state
y
m
.
15
Then let
r
m
be
r
m
−
1
followed by
p
m
.In other words
r
m
=
⊕
m
i
=1
p
i
,
where
⊕
denotes concatenation.
16
By Corollary 4.7, once
f
is sufficiently large, any
f
-fast reaction
sequence from
x
m
to
y
m
must be Π-friendly. Thus by reindexing (
x
m
) to start with a sufficiently
large member of the sequence, we have that for all
m
,
x
m
=
⇒
Π
y
m
.
By Dickson’s Lemma there is an infinite nondecreasing subsequence
Y
= (
y
s
1
,
y
s
2
,...
). Let Γ =
{
S
∈
Λ
|
lim
n
→∞
y
s
n
(
S
) =
∞ }
. By Proposition 4.6, Γ
⊆
Π since
x
s
n
=
⇒
Π
y
s
n
. Let ∆ = Π
\
Γ.
These are the species that are “large” in (
x
m
) but are bounded in
Y
. By the definition of Γ, there
is a constant
c
such that, for all
n
∈
N
and
S
∈
∆,
y
s
n
(
S
)
< c
. Thus an infinite subsequence of
y
s
n
’s has equal counts of all species
S
∈
Λ
\
Γ. Since counts of species in Γ grow without bound as
n
→∞
, there is an infinite subsequence of
that
on which
every
element of Γ has its count strictly
increase on each subsequent
y
s
n
state. We therefore assume that
Y
= (
y
s
1
,
y
s
2
,...
) is exactly this
infinite subsequence (to avoid introducing yet more variable names), where each
y
s
n
(
S
) =
y
s
n
+1
(
S
)
if
S
∈
Λ
\
Γ and
y
s
n
(
S
)
<
y
s
n
+1
(
S
) if
S
∈
Γ.
Recall that a state is
committed
if it cannot produce a YES voter. The next lemma shows that
changing counts of pumpable species (Π) by a “small” amount in
x
m
, so long as
m
is sufficiently
large, cannot change the ability of
x
m
to reach a committed state. Intuitively, later on
e
will
represent a change in counts due to “processing” the extra copy of
A
1
(the one that changes the
correct answer in state
i
n
(
n
1
,...,n
k
) from NO to YES), and the following lemma will help us to
derive a contradiction because the extra copy of
A
1
should enable the production of a YES voter.
Lemma 4.11.
Let sequences
(
x
m
)
and
(
y
m
)
be as defined above. For all
∈
N
, there exists
′
∈
N
such that the following holds. For all
e
∈
Z
Π
with
|
e
| ≤
, for infinitely many
m
, there exists
e
m
∈
Z
Γ
with
|
e
m
|≤
′
, and
m
2
< m
such that
x
m
+
e
=
⇒
Π
y
m
2
+
e
m
and
y
m
2
+
e
m
is committed.
15
Let
f
m
=
f
m
−
1
+ 1 if there are
f
-fast paths from
y
m
−
1
+
d
to
y
m
for all
f
∈
N
; this may occur if there are
reactions such as
X
→
X
+
F
that can generate arbitrarily large counts of some molecules without consuming others.
16
By the definition of speed fault free, lim
m
→∞
f
m
=
∞
, since
x
m
and
y
m
for increasing
m
are reachable from
input states
i
n
with increasing amounts of fuel.
13