Strong Turing Completeness 113input there exists an ODE system computing the result. Here this is auniform
computabilityresult: a given polynomial differential equation is able to simulate
a Turing machine on all inputs, independently of the size of the input.
In order to be more concrete on the encoding of Turing machines, let us
rephrase [ 6 ]. One can fix a finite alphabetΓ={ 0 , .., k− 2 }and encode a word
w=w 1 w 2 ...w|w|by the coupleψ(w)=
(∑
|w|
i=1wik
−i,|w|)
. There is nothing
special about this encoding, other encodings may be used, however, two crucial
properties are necessary: (i)ψ(w) must provide a way to recover the word without
ambiguity, (ii)||ψ(w)||isO(|w|). In particular, over the alphabetΓ={ 0 , 1 },
the use of base 3 (instead of base 2) simplifies the decoding.
Now consider any decision problem (language)L⊂Γ∗.IfLis decidable,
then there is a Turing machine that decides it. Then [ 6 ] provides (effectively
from the Turing machine) some polynomial vectorsp∈Rn[Rn] and a polynomial
q∈Rn[R] such that for allw∈Γ∗there is a (unique)y:R+→Rdsuch that
for allt∈R+:
1.y(0) =q(ψ(w)) andy′(t)=p(y(t)) with||y′(t)|| ≥1,
- if|y 1 (t)|1 for sometthen|y 1 (u)|1 for allut(the decision is stable)
- ifw∈L(resp.∈L/ ) then there is sometwithy 1 (t)1(resp.−1)
Furthermore, ifLis decided in polynomial time (i.e. is in class PTIME) then
there is some polynomialΩ(that can be obtained effectively from the polynomial
bound forLand from the Turing machine) such that this happens in polynomial
length: condition 3.is replaced by
- ifw∈L(resp.∈L/ )and
∫t
0 ||y′(τ)||dτ≥Ω(|w|) theny 1 (t)1(resp.−1)In other words, [ 6 ] is considering a notion of termination given by the fact
that some variable becomes of absolute value greater than 1: if the value is
greater than 1 (respectively: less than−1) this corresponds to acceptance (resp.
rejection). Other criteria for acceptance could be considered as seen from the
proofs of [ 6 ]. The fact that the acceptance region is at some distance from the
rejectance region (a value between−1 and 1 means the absence of decision) is
here only to avoid representation problems if one wants to simulate the involved
equations.
Notice that [ 6 ] was leaving open the issue whether the involved polynomial
in the polynomial ordinary differential equations could have non-rational coeffi-
cients (notice that the constructions were however using only computable coef-
ficients, but possibly irrational). It has been proved recently that only rational
coefficients are needed [ 3 ].
The notion of uniform computability is the strong notion of Turing univer-
sality involved in the rest of this paper.
3 Turing Completeness of Elementary Chemical Reaction
Networks
The previous results provide a solid foundation for studying biochemical ana-
log computation. However, a biochemical reaction system is apositivedynamical