Computational Methods in Systems Biology

Strong Turing Completeness 115

Definition 8.Afunctionf:R+→R+ischemically-computableif there exist
a mass-action-law reaction system{(Ri,Pi,fi)}i∈Iover some molecular species
{y 1 ,...,yn}, and a polynomialq∈R+n[R+]defining the initial concentration
values, such thatf is GPAC-computed byq and its (polynomial) differential
semanticsp∈R+n[R+n].
Afunctionf:R+→Rischemically-computableif there exists a chemi-
cally computable functionf+:R+→R+^2 (by straightfortward generalization
of Definition 4 to multiple computations) over{y 1 +, ..., yn+,y− 1 , ..., y−n}such that
f=f 1 +−f 2 −.

In this definition, to computef(x), one has thus to design a reaction system
over a finite set of molecular species, initialized to some values defined by a vector
of polynomialsq(x) (e.g. following [ 8 , 12 ]), which guarantees that the result is
obtained in the concentration of one distinguished molecular species, with a
precision indicated by another distinguished molecular species (see Definition 4 ).
Note however that in practice, in the examples of the following sections, the
precision parameter will be left.
How to design such a reaction system is shown by the proofs of the following
results.

Theorem 3.Any GPAC-computable function can be computed by a mass-
action-law reaction system under the differential semantics preserving the poly-
nomial length complexity.

Proof.Let us consider a GPAC-computable function by a polynomial differential
equationp∈Rn[Rn]. Each variableyi ∈Rcan be encoded by a couple of
variables (y+i,y−i)∈R^2 +such that at any time,yi=y+i −y−i.
Let ˆpi(y+ 1 ,y− 1 ,...,y+n,yn−)=pi[y=y+−y−], we write ˆpi=ˆp+i −pˆ−i, where
the monomials of ˆp+i and ˆp−i have positive coefficients. A positive system is then
defined by:

∀i≤n,

⎧

⎪⎪

⎨

⎪⎪

⎩

y+i

′

=ˆp+i −fiy+iyi−

y−i

′

=ˆp−i −fiy+iy−i

y+i(0) = max(0,yi(0))

y−i(0) = max(0,−yi(0))

where the fi’s are polynomials with positive coefficients such that fi ≥
max(ˆp+i,pˆ−i), for instancefi=ˆp+i +ˆp−i. The terms−fiyi+y−i can be imple-
mented by annihilation reactions

fiforyi++yi−

y+,y−

−−−−→

which ensure that one of theyi±always remains small.

Note that we have:yi+
′
≤pˆ+i(1−yi+yi−)andy−i
′
≤pˆ−i(1−y+iy−i), so that
(yi+yi−)′ ≤q·(1−y+iy−i) whereq is a polynomial with positive coefficients.
Since att=0wehaveyi+y−i = 0, we deduce by a Gronwall inequality that
we always havey+iyi− ≤1. Therefore,|y±i|≤|yi|+1, and|y±|≤|y|+n.
Consequently, if the original system is increased in space by a polynomial in the
size of the input and the time, then this is still the case for the positive system