An analog characterization of the Grzegorczyk hierarchy.
We study a restricted version of Shannon's general purpose analog computer in which we only allow the machine to solve linear differential equations. We show that if this computer is allowed to sense inequalities in a differentiable way, then it can compute exactly the elementary functions, the smallest known recursive class closed under time and space complexity. Furthermore, we show that if the machine has access to a function f(x) with a suitable growth as x goes to infinity, then it can compute functions on any given level of the Grzegorczyk hierarchy. More precisely, we show that the model contains exactly the nth level of the Grzegorczyk hierarchy if it is allowed to solve n - 3 non-linear differential equations of a certain kind. Therefore, we claim that, at least in this region of the complexity hierarchy, there is a close connection between analog complexity classes, the dynamical systems that compute them, and classical sets of subrecursive functions.
INTRODUCTION
The theory of analog computation, where the internal states of a computer
are continuous rather than discrete, has enjoyed a recent resurgence
of interest. This stems partly from a wider program of exploring alternative
approaches to computation, such as quantum and DNA computation;
partly as an idealization of numerical algorithms where real numbers can
be thought of as quantities in themselves, rather than as strings of digits;
and partly from a desire to use the tools of computation theory to better
classify the variety of continuous dynamical systems we see in the world
(or at least in its classical idealization).
However, in most recent work on analog computation (e.g. [BSS89, Mee93,
Sie99, Moo98]) time is still discrete. Just as in standard computation the-
ory, the machines are updated with each tick of a clock. If we are to make
the states of a computer continuous, it makes sense to consider making its
progress in time continuous too. While a few eorts have been made in the
direction of studying computation by continuous-time dynamical systems
[Moo90, Moo96, Orp97b, Orp97a, SF98, Bou99, CMC00], no particular set
of denitions has become widely accepted, and the various models do not
seem to be equivalent to each other. Thus analog computation has not yet
experienced the unication that digital computation did through Turing's
work in 1936.
In this paper, as in [CMC00], we take as our starting point Claude Shan-
non's General Purpose Analog Computer (GPAC). This was dened as
a mathematical model of an analog device, the Dierential Analyser, the
fundamental principles of which were described by Lord Kelvin in 1876
[Kel76]. The Dierential Analyser was developed at MIT under the supervision
of Vannevar Bush and was indeed built in for the rst time in 1931
[Bow96]. Its input was the rotation of one or more drive shafts and its
output was the rotation of one or more output shafts. The main units were
interconnected gear boxes and mechanical friction wheel integrators.
Just as polynomial operations are basic to the Blum-Shub-Smale model
of analog computation [BSS89], polynomial dierential equations are basic
to the GPAC. Shannon [Sha41] showed that the GPAC generates exactly
the dierentially algebraic functions, which are unique solutions of polynomial
dierential equations. This set of functions includes simple functions
like e x and sin x as well as sums, products, and compositions of these, and
solutions to dierential equations formed from them such as f
Pour-El [Pou74], and later Lipshitz and Rubel [LR87], extended Shannon's
work and made it rigorous.
The GPAC also corresponds to the lowest level | we denote here by
G | in a theory of recursive functions on the reals proposed by Moore
[Moo96]. There, in addition to composition and integration, a zero-nding
operator analogous to the minimization operator  of classical recursion
theory is included. In the presence of a liberal semantics that denes
even when f is undened on x, this permits contraction
of innite computations into nite intervals, and renders the arithmetical
and analytical hierarchies computable through a series of limit processes
similar to those used by Bournez [Bou99]. However, such an operator is
clearly unphysical, except when the function in question is smooth enough
for zeroes to be found in some reasonable way.
In [CMC00] a new extension of G was proposed. The operators of the
GPAC were kept the same | integration and composition | but piecewise-
analytic basic functions were added, namely  k
the Heaviside step function,
Adding one of these functions,  k for some xed k, as an 'oracle' can be
thought of as allowing an analog computer to measure inequalities in a
1)-times dierentiable way. These functions are also unique solutions of
dierential equations such as xy two boundary conditions
rather than just an initial condition, which is a slightly weaker denition
of uniqueness than that used by Pour-El to dene GPAC-computability.
By adding these to the set of basic functions, for each k we get a class we
denote by G
A basic concern of computation theory is whether a given class of functions
is closed under various operations. One such operation is iteration,
where from a function f(x) we dene a function F (x;
applied t times to x, for t 2 N. The main result of [CMC00] is that G
is closed under iteration for any k  0, while G is not. (Here we adopt the
convention that a function where one or more inputs are integers is in a
given analog class if some extension of it to the reals is.) It then follows
that G includes all primitive recursive functions, and has other closure
properties as well.
To rene these results, in this paper we consider a restricted version of
Shannon's GPAC. In particular, we restrict integration to linear integra-
tion, i.e. solving linear dierential equations. We dene then a class of
computable functions L whose operators are composition and linear integration
and then add, as before, a basic function  k for some xed k > 2.
The model we obtain, L+  k , is weaker than G . One of the main results
of this paper is that, for any xed k > 0, L+ k contains precisely the
elementary functions, a subclass of the primitive recursive functions introduced
by Kalmar [Kal43] which is closed under the operations of forming
bounded sums and products. Inversely, using Grzegorczyk and Lacombe's
denition of computable continuous real function [Grz55, Lac55], we show
that all functions in L+ k are elementarily computable for any xed k > 2,
and that if a function f 2 L+  k is an extension to the reals of some function
4~
f on the integers, then ~
f is elementary as well. 1 Thus we seem to have
found a natural analog description of the elementary functions, the smallest
known recursive class closed under time and space complexity [Odi00].
To generalize this further, we recall that Grzegorczyk [Grz53] proposed
a hierarchy of computable functions that straties the set of primitive recursive
functions. The elementary functions are simply the third level of
this hierarchy. We show that if we allow L to solve n 3 non-linear
dierential equations of a certain kind, then all functions in the nth level
of the Grzegorczyk hierarchy have extensions to the reals in the resulting
analog class. A converse result also holds.
Therefore, we claim that there is a surprising and elegant connection
between classes of analog computers on the one hand, and subclasses of
the recursive functions on the other. This suggests, at least in this region
of the complexity hierarchy, that analog and digital computation may not
be so far apart.
The paper is organized as follows. In Section 2 we review classical recursion
theory, the elementary functions, and the Grzegorczyk hierarchy.
In Section 3 we recall some basic facts about linear dierential equations.
Then, in Section 4 we dene a general model of computation in continuous
time that can access a set of 'oracles' or basic functions, compose these,
and solve linear dierential equations. We call this class L or more
generally for a set of oracles '.
We then prove bounds on the growth of functions denable in L
The existence of those bounds allows us to prove the main lemma of the
paper, which shows that L+  k is closed under forming bounded sums and
bounded products. With this, we are able to prove that L contains
extensions to the reals of all elementary functions. Inversely, we show that
all functions in are elementarily computable. This shows that the
correspondence between L+ k and the elementary functions is quite robust.
Then, in Section 5 we consider the higher levels in the Grzegorczyk hierarchy
by dening a hierarchy of analog classes Gn Each one of these
classes is dened similarly to L that our model is now allowed
to solve up to n 3 non-linear dierential equations, of a certain kind,
which produces iterations of functions previously dened. We then show
that this hierarchy coincides, level by level, with the Grzegorczyk hierarchy
in the same sense that L coincides with the elementary functions.
Finally, we end with some remarks and open questions.
1 The approach we follow [Ko91, Pou74, Wei00] to describe the complexity of real
functions is eective, in the sense that it extends standard complexity theory and relies
on the Turing machine as the model of computation to dene computability and
complexity. A distinct approach is to consider reals as basic entities as in [BSS89].
2. SUBRECURSIVE CLASSES OVER N AND THE
In classical recursive function theory, where the inputs and output of
functions are natural numbers N, computational classes are often dened
as the smallest set containing a set of initial functions and closed under certain
operations, which take one or more functions in the class and create
new ones. Thus the set consists of all those functions that can be generated
from the initial ones by applying these operations a nite number of
times. Exemples of common initial functions are zero, successor, projections
x  y and 0 if x < y. Typical operations include (where ~x represents a
vector of variables, which may be absent):
1. Composition: Given an n-ary function f and a function g with n
2. Primitive recursion: Given f and g of the appropriate arity, dene h
such that h(~x;
3. Bounded sum: Given f(~x; y), dene h(~x;
z<y f(~x; z).
4. Bounded product: Given f(~x; y), dene h(~x;
z<y f(~x; z).
By starting with various sets of basic functions and demanding closure
under various properties, we can dene various natural classes. In partic-
ular, we will consider:
Primitive recursive functions are those that can be generated from zero,
successor, and projections using composition and primitive recursion.
Elementary functions are those that can be generated from zero, suc-
cessor, projections, addition, and cut-o subtraction using composition and
the operation of forming bounded sums and bounded products.
In classical recursive function theory more general objects called
which take an innite sequence and a nite
number of integers as input, can be dened. To dene a functional we
add a new operation A(; which accesses the x-th element of a
given innite sequence . When A is not used in the recursive denition
of ,  degenerates into a function. In particular we say that a functional
is elementary if it can be generated from the basic functionals
y, F (; x;
using composition, bounded sums and bounded prod-
ucts. We will need this notion of elementary functional in Proposition 4.4.
The class of elementary functions, which we will call E , was introduced by
Kalmar [Kal43]. As examples, note that multiplication and exponentiation
over N are both in E , since they can be written as a bounded sum and a
bounded product respectively:
z<y x and x
z<y x. Since E
is closed under composition, for each m the m-times iterated exponential
In fact, no
elementary function can grow faster than 2 [m] for some xed m, and many
of our results will depend on the following bound on their growth [Cut80]:
Proposition 2.1. If f 2 E, there is a number m such that, for all ~x,
The elementary functions are exactly the functions computable in elementary
time [Cut80], i.e., the class of functions computable by a Turing
machine in a number of steps bounded by some elementary function.
The class E is therefore very large, and many would argue that it contains
all practically computable functions. It includes, for instance, the
connectives of propositional calculus, functions for coding and decoding sequences
of natural numbers such as the prime numbers and factorizations,
and most of the useful number-theoretic and metamathematical functions
[Cut80, Ros84]. However, Proposition 2.1 shows that it does not contain
the iterated exponential 2 [m] (x) where the number of iterations m is a
variable, since any function in E has an upper bound where m is xed.
The iterated exponential is, however, primitive recursive. As a matter
of fact, it belongs to one of the lowest levels of the Grzegorczyk hierarchy
[Grz53, Ros84], which measures the structural complexity of the class of
primitive recursive functions, and we review below.
Let's rst recall what a LOOP-program is. It is a program which can
be written in a programming language with assignments, conditional and
FOR statements, but with no WHILE or GO-TO statements. Notice that
a LOOP-program always halts. The primitive recursive functions are precisely
the functions that are computed by LOOP-programs. We can stratify
them considering the subclasses of functions computable by LOOP-
programs with up to n nested FOR statements. For this gives the
elementary functions [HW99], and for n  2 this gives precisely E n+1 , the
1-th level of the Grzegorczyk hierarchy.
Originally [Grz53], the Grzegorczyk hierarchy was dened recursively.
The elementary functions are the third level of the Grzegorczyk hierarchy,
. For the following levels we consider a family of functions
N. These are, essentially, repeated iterations of the successor
function, and each one grows qualitatively faster than the previous one.
composing it yields functions as large as
2 [m] for any xed m. Iterating
In general, En+1
can be dened with
En 1 and closure under bounded sums and products (cf. [Odi00]):
(The Grzegorczyk hierarchy) For n  3, E n is the smallest class containing
zero, successor, the projections, cut-o subtraction, and En 1 , which
is closed under composition, bounded sum, and bounded product.
The union of all the levels of the Grzegorczyk hierarchy is the class PR
of primitive recursive functions, i.e.,
We can also generalize Proposition 2.1 and put a bound on the growth
of functions anywhere in the Grzegorczyk hierarchy:
Proposition 2.2. If n  2 and f 2 E n then there is an integer m such
that f(~x)  E [m]
3. LINEAR DIFFERENTIAL EQUATIONS
An ordinary linear dierential equation is a dierential equation of the
where A(t) is a n  n matrix whose entries are functions of t and ~ b(t) is a
vector of functions of t. If ~ we say that the system is homogeneous.
We can reduce a non-homogeneous system to a homogeneous one by introducing
an auxiliary variable xn+1 such that xn+1 t, that is,
which satises xn+1
The new matrix will just be
This matrix is not invertible, which makes (1) harder to solve. However,
since we don't need to solve the system explicitly, we prefer to consider the
homogeneous equation
as the general case in the remainder of the paper.
This leads to the original denition of the Grzegorczyk hierarchy (cf. [Clo99]).
The fundamental existence theorem for dierential equations guarantees
the existence and uniqueness of a solution in a certain neighborhood of an
initial condition for the system ~x when f is Lipschitz. For linear
dierential equations, we can strengthen this to global existence whenever
A(t) is continuous, and establish a bound on ~x that depends on kA(t)k. 3
Proposition 3.1 ([Arn96]). If A(t) is dened and continuous on an
interval I = [a; b], where a  0  b, then the solution of Equation 2 with
initial condition dened and unique on I. Furthermore, if
kA(t)k is non-decreasing this solution satises
Therefore, if A(t) is continuous and non-decreasing on R then solutions
of linear dierential equations are dened on arbitrarily large domains and
have an exponential bound on their growth that depends only on kA(t)k.
Proposition 3.1 holds both for the max norm,
and for the Euclidean norm [Har82]. If we use the max norm, which satises
when the conditions of Proposition 3.1 are fullled.
4. THE ANALOG CLASS L
FUNCTIONS
In [Moo96, CMC00] a denition of Shannon's General Purpose Analog
Computer (GPAC) in the framework of the theory of recursive functions
on the reals is given. We denote the corresponding set of functions by
G. It is the set of functions that can be inductively dened from the constants
0, 1, and 1, projections, and the operations of composition and
integration. Integration generates new functions by the following rule: if
f and g have appropriate arities and belong to G then the function h dened
by the initial condition h(~x; and the dierential equation
@ y h(~x; also belongs to G, over the largest interval containing
0 on which the solution is nite and unique. Thus G has the power
3 By k  k we denote both the norm of a vector and the norm of a matrix, with
1g. By A being continuous, respectively increasing, we mean
that all entries of A are continuous, respectively increasing, functions.
to solve arbitrary initial value problems with unique solutions, constructed
recursively from functions already generated.
We dene here a proper subclass of G which we call L, by restricting the
integration operator to solving time-varying linear dierential equations.
To make the denition more general, we add a set of 'oracles' or additional
basic functions. Let ' be a set of continuous functions dened on R k for
some k. Then L+' is the class of functions of several real variables dened
recursively as follows:
Definition 4.1. A function h belongs to L its components
can be inductively dened from the constants 0, 1, 1, and , the
projections U i functions in ', and the following operators:
1.Composition: if a p-ary function f and a function g with p components
belong to L+', then dened as belongs to L+'.
2.Linear integration: if f and g are in L+' then the function h satisfying
the initial condition h(~x; solving the dierential equation
@ y h(~x;
belongs to L vector-valued with n components, then f has the
same dimension and g(~x; y) is an n  n matrix whose components belong
to As shorthand, we will write
R
gh dy.
Several notes on this denition are in order. First, note that linear
integration can only solve dierential equations @ y gh where the right-hand
side is linear in h, rather than the arbitrary dependence @ y
which the GPAC is capable. Secondly, using the same trick as in Section 3
we can expand our set of variables, and so solve non-homogeneous linear
dierential equations of the form
@ y h(~x;
Finally, the reader will note that we are including  as a fundamental
constant. The reason for this will become clear in Proposition 4.7. Unfor-
tunately, even though it is easy to show that  belongs to G, we have not
found a way to derive  using this restricted class of dierential equations.
Perhaps the reader can do this, or nd a proof that we cannot.
We will use the fact that, unlike solving more general dierential equa-
tions, linear integration can only produce total functions:
Proposition 4.2. All functions in L+' are continuous and are dened
everywhere.
Let us look at a few examples. Addition, as a function of two variables,
is in L since Similarly, multiplication
can be dened as
is in L since it can be dened as
by using either composition or linear integration,
with exp [2] (Note that
we are now using e rather than 2 as our base for exponentiation.)
Thus the iterated exponential exp [m] is in L for any xed m. However,
the function exp [n] (x), where the number of iterations is a variable, is
neither in L nor in G. We prove this in [CMC00], and use it to show that
Shannon's GPAC is not closed under iteration. However, if G is extended
with a function  k , for k  0, then the resulting class G + k is closed under
iteration, where  k is dened as follows.
is the Heaviside step function
Each  k (x) can be interpreted as a function which checks inequalities such
as x  0 in a (k 1)-times dierentiable way (for k > 1). It was also shown
in [CMC00] that allowing those functions is equivalent to relaxing slightly
the denition of GPAC by solving dierential equations with two boundary
values instead of just an initial condition.
In this section we consider L and prove that for any xed k > 2
this class is an analog characterization of the elementary functions. We
will start by noting that all functions in L+  k have growth bounded by a
nitely iterated exponential, exp [m] for some m. This is analogous to the
bound on elementary functions in Proposition 2.1, and can easily be proved
by structural induction, using the bound in Proposition 3.1.
Proposition 4.3. Let h be a function in L+  k of arity m. Then there
is a constant d and constants A; B; C; D such that, for all ~x
j. The least d for which there are such A; B; C; D
will be called the degree of h or deg h.
Propositions 2.1 and 4.3 establish the same kind of bounds for E and
. But the relation between those two classes can be shown to
be much tighter: namely, all functions in can be approximated by
elementary functions, and all extensions to the reals of elementary functions
are contained in L
Since E is dened over the natural numbers and L is dened over
the reals, we rst need to set some conventions.
(Convention 1) We say that a function over the reals is elementary if it
fullls Grzegorczyk and Lacombe's denition of computable continuous real
function [Grz55, Grz57, Lac55, PR89] and if the corresponding functional
is elementary. First, we write S ; a if an integer sequence
N. Note that, by dividing
denition allows sequences of integers to converge to real
numbers. To dene computability of real functions that range over R with
elementary functions and functionals dened on N we use a simple bijective
encoding
and we say a real number a 2 R is
elementarily computable if there is an elementary function s
that Finally, a continuous real function f
is elementarily computable if there is an elementary functional  which,
for all a 2 R and for all sequences  : N ! N such that  -  ; a,
denotes the sequence
:g. The denition for vector-valued functions
and functions of several variables is similar.
The denition above can be extended in a straightforward manner to
-computability. This was already described in [Zho97], where f is said
to be E n -computable if: (1) f maps every E n -computable sequence of reals
into an E n -computable sequence of reals; and (2) there is a function d in E n
such that jx yj < 1=d(k) implies jf(x) f(y)j < 1=(k+1) for all x; y in any
bounded domain of f . We notice that time and space complexity for
functions, with n  3, can alternatively be dened using a function oracle
Turing machine as the model of computation [Ko91, Wei00]. For example,
a function f is elementary if f(x) can be computed with precision 1=n in
a number of steps elementary in jxj and n.
(Convention Conversely, we say that contains a function f
contains some extension of f to the reals, and similarly for
functions of several variables. These two conventions allow us to compare
analog and digital complexity classes.
Proposition 4.4. If f belongs to L
f is elementarily computable.
Proof. Once again, the proof will be done by structural induction. To
keep the notation simpler, we won't include the encoding function  in
the proof. It is clear that the constants 0, 1, 1 and  are elementarily
computable (e.c. for short). U i (~x) is simply x i and is obviously e.c., and
k (x) is e.c. since and polynomials are in E and the parity of x is computable
in E too.
For simplicity, we prove that composition of e.c. functions is also e.c. just
for real functions of one variable. The proof is similar for the general case.
If g is e.c. then there is a functional  g such that  g (;
sequence  ; a, and if f is e.c. then there is a functional  f such that
sequence ' ; b. Setting
f(g(a)). Since the composition of two elementary functionals is elementary,
we are done.
Finally, we have to show that if f and g are e.c. then h such that h(~x;
f(~x) and @ y h(~x; is also. This means that we have to
show that there is an elementary functional such that (;
for all sequences
We will do this using standard numerical techniques, namely Euler's
method. Let us suppose that h 2 L+ k is twice continuously dierentiable,
which is guaranteed if k > 2. 4 Fixing ~x and expanding h we obtain
for some  where  i <  <  i+1 . Since g is e.c. there is an elementary
functional  g such that  g (; To obtain
an estimate of the value of g on (~x;  i ), we set
1). The
accuracy of this estimate depends on n since k
We will set below a lower bound for n.
The discrete approximation of h is then simply done by Euler's method,
where the  i 's are the discretization steps, and we will show that we can
make the discretization error su-ciently small with an elementary number
of discrete steps. 5 We dene a function by
where the step size of the discretization are to be
xed by the number of steps of the numerical approximation. We dene
now an elementary functional . For each xed ~x and any sequence  ; y,
(; l) is dened as being the integer closest to (l + 1) N , where N is a
suitably increasing elementary function of l and where N is obtained using
4 We don't study the particular cases since we are mainly interested in
the properties of L+  k for large k, i.e., when L+  k only contains \smooth" functions.
5 When xed point numerical calculations are used, there is also a round-o error.
However, in the worst case, the acumulated round-o error is of the same order of the
discretization error (cf. [Har82, 3.4.4] and [VSD86]). Therefore, we will only study the
discretization error of the numerical approximation.
a discretization step
(l
in (5). Note that then (; l) is always an integer as required by the
denition, and k(; l)=(l
We will now show how to choose n, m and N as functions of l such that
To prove that this
can be done in elementary time, we rst need to set a bound on
Since h 00 can be written as the sum and product of functions with bounds
of the form A exp [d] (Bk(~x; t)k), from Proposition 4.3, then kh 00 (~x; t)k is
bounded by A exp [d] (Bk(~x; t)k) for some d, A and B. We will call this
bound  and we will denote by  a number larger than (~x; y), for instance,
y, for any l and any  ; y.
The discretization error is
and satises
Furthermore, because f is e.c.,
where  f is the elementary functional that computes f . A little tedious
algebra shows then that
Therefore, given , which is elementary, it su-ces to set
to guarantee that k N
l. Note that, since n, m and N are elementary functions of l,  can
be computed in elementary time. Therefore, by the triangle inequality,
Finally, we just have to show
how to dene from  another elementary functional such that (;
be the integer closest to
1). is elementary since it is a composition of  and
which is an elementary function. Since, for all l and  ; y, kh(~x; y)
little more algebra allows us to show that
This concludes the proof.
As a corollary, any function in L that sends integers to integers is
elementary on the integers:
Corollary 4.5. If a function f 2 L is an extension of a function
~
f is elementary.
Proof. Proposition 4.4 shows us how to successively approximate f(x) to
within an error  in an amount of time elementary in 1= and x. If f is an in-
teger, we just have to approximate it to error less than 1=2 to know its value
exactly.
Next we will prove the converse of this, i.e. that L contains all
elementary functions, or rather, extensions of them to the reals. We will
rst prove two lemmas.
Lemma 4.6. For any xed k > 0, L contains sin, cos, exp, the
constant q for any rational q, and extensions to the reals of successor,
addition, and cut-o subtraction.
Proof. We showed above that L+ k includes addition, and the successor
function is just addition by 1. For subtraction, we have x
@ y
We can obtain any integer by repeatedly adding 1 or 1. For rational
constants, by repeatedly integrating 1 we can obtain the function
z k =k! and thus k. We can multiply this by an integer
to obtain any rational q.
For cut-o subtraction x : y, we rst dene a function s(z) such that
Z. This
can be done in L by setting
R 1z k (1 z) k dz is a rational constant depending on k. Then
is an extension to the reals of cut-o subtraction.
Finally, dened by
with exp as proved above.
We now show that L has the same closure properties as E , namely
the ability to form bounded sums and products.
Lemma 4.7. Let f be a function on N and let g be the function on N
dened from f by bounded sum or bounded product. If f has an extension
to the reals in L does also.
Proof. For simplicity, we give the proof for functions of one variable.
We will abuse notation by identifying f and g with their extensions to the
reals.
We rst dene a step function F which matches f on the integers, and
whose values are constant on the interval j. F can
be dened as F is a function such that
and s 0
R 1=2sin k 2t dt is a constant
depending only on k. Since c k is rational for k even and a rational multiple
of  for k odd, s is denable in L (Now our reasons for including
in the denition of L
The bounded sum of f is easily dened in L by linear integra-
tion. Simply write
Dening the bounded product of f in L +  k is more di-cult. Let
us rst set some notation. Let f j denote f(j) for j 2 N, which is also
equal to F (t) for t 2
the bounded product we wish to dene. The idea of the proof is to approximate
the iteration g using synchronized clock functions as
in [Bra95, Moo96, CMC00]. However, since the model we propose here
only allows linear integration, the simulated functions cannot coincide exactly
with the bounded product. Nevertheless, we can dene a su-ciently
close approximation because f and g have bounded growth by Proposition
4.3. Then, since f and g have integer values, the accumulated error
resulting from this approximation can be removed with a suitable continuous
step function r simply dened by
returns the integer closest to t
as long as the error is 1=4 or less.
Now dene a two-component function ~y(; t) where y 1 (;
1 and
where () is an increasing function of  . Then we claim that
r(y 1 (n; n)). We will see that if  grows quickly enough, then by setting
we can make the approximation error jy 1 (n; n) g n j as small as we
like, and then remove the error by applying r.
Again, the idea is that on alternate intervals we hold either y 1 or y 2
constant and update the other one. For integer j, it is easy to see that
when the term  k ( sin 2t) holds y 2 constant, and y 1
moves toward y 2 f(j). Quantitatively, solving (7) for t 2
Similarly,
when held constant and y 2 moves toward y 1 . This
gives us the recursion
Note that if () is su-ciently small then
Now let are
bounded from above by A exp [m] (Bn) as in Proposition 4.3. Below we
show that we can set for instance adjusting m, and that
for all m;n  1. Since this is less than 1=4, we can round the value of y 1
to the nearest integer using r, as claimed.
To conclude the proof, we show that jy 1 (n; n) g n j < 1=4 . Without loss
of generality, we will set the constants in the bound on f and g to A = 3
since A exp [m] (B) can always be bounded by 3 exp [m 0 ] () with
large enough. Also to simplify the notation, we will denote y 1 (n;
and y 2 (n; j) by y 1 (j) and y 2 (j), respectively. We will prove that jy 1 (n)
for all m;n  1. We will proceed by induction on j for
Recall that y 1
Equation 8 shows that jy 1 (1) f 0 j  j1 f 0 j   and that
We will now show
that if
and
then
and
for all j  n 1, when f
First, note that from (9), (10) and the triangle inequality, we obtain
To prove (11) from (9) and (10) we use the recursion of Equation 8 and
the bounds on f j and g j . From (8) we have
From (9) we can write y 1
from (13), y 2 . Then (14) can be
rewritten as
which is
Therefore,
Since  is small and  is large then the rst term dominates the others
and, consequently, we have jy 1 (j
claimed. The proof that (9) and (10) imply (12) is similar.
Finally, we brie
y show that 2 4n (n which is always positive,
is smaller than 32:9:e 4 =e 3e 2
we obtain the
previous value. It is easy to verify that
decreases when m and n increase.
We illustrate this construction in Figure 1. We approximate the bounded
product of the identity function, i.e. the factorial (n
j<n j. We
y 1,2
FIG. 1. A numerical integration of Equation (7), where f is a L+  k function such
that 2. We obtain an approximation of an
extension to the reals of the factorial function. In this example, where we chose a small
< 4, the approximation is just su-cient to remove the error with  and obtain exactly
(5)).
numerically integrated Equation (7) using a standard package (Mathemat-
ica).
An interesting question is whether L+ k is closed under bounded product
for functions with real, rather than integer, values. Our conjecture is that
it is not, but we have no proof of this.
From the previous two lemmas it follows that
Proposition 4.8. If f is an elementary function, then L+  k contains
an extension of f to the reals.
Taken together, Propositions 4.4 and 4.8 show that the analog class L+ k
corresponds to the elementary functions in a natural way.
5. Gn
In this section we show that we can extend the results of the previous
section to the higher levels of the Grzegorczyk hierarchy, E n for n  3.
Let us dene a hierarchy of recursive functions on the reals. Each level is
denoted by Gn 3. The rst level is G 3
and each following level is dened either by adding a new basic function, or
by allowing the system to solve a certain number of non-linear dierential
equations.
Definition 5.1 (The hierarchy Gn k be the
smallest class containing the constants 0, 1, 1, and , the projections, and
which is closed under composition and linear integration, and dened
up to n 3 applications of the following operator:
Non-linear integration (NLI): if a unary scalar funtion f belongs to Gn
then the solution of the initial value problem
with initial condition y 1 belongs to Gn
We will now show that Gn xed k > 2, corresponds to
the nth level of the Grzegorczyk hierarchy in the same way that
corresponds to the elementary functions. First, we will show the operator
NLI carries us up the levels of the Gn just as iteration does
for the
Proposition 5.2. For any function f 2 Gn there is an extension
of the iteration F (x;
Proof. F (x; t) is given by y 1 in the Equation (15) with the initial conditions
x. Note that jxj k can dened in L
it can be proved that, for all t 2 N, y 1
The function y 1 belongs to Gn+1 since it is dened from f , which is in
only one application of NLI. The dynamics for Equation (15)
is similar to Equation (7) for iterated multiplication, in which y 1 and y 2
are held constant for alternating intervals. The main dierence is that the
terms jcos tj k+1 and jsin tj k+1 on the left ensure that y 1 converges exactly
to f(y 2 ), and y 2 exactly to y 1 , by the end of the interval [n; n+1]. The term
k (t) on the right ensures that the solution is constant y 1
for t < 0. The proof is similar to the one given in [CMC00, Proposition 9].
Now dene a series of functions exp
for x 2 N. Since exp 2 2 L+ k , Proposition 5.2 shows that Gn contains
extensions to the reals of exp n 1 for all n  3. Since
tary, an extension of it to the reals belongs to L by Proposition 4.8,
and since En+1 is dened from En by iteration, Gn contains extensions
to the reals of En 1 for all n  3. For simplicity, we will also use
the notation exp n (x) and En (x) for monotone extensions of exp n and En
to x 2 R.
In fact, nite compositions of exp n 1 and En 1 put an upper bound on
the growth of functions in Gn so in analogy to Proposition 4.3 we have
the following:
Proposition 5.3. Let f be a function of arity m in Gn
3. Then there is a constant d and constants A; B; C; D such that, for
all x
kf(~x)k  A exp [d]
j. Moreover, the same is true (with dierent con-
stants) if exp n 1 is replaced by En 1 .
Now, as before, to compare an analog class to a digital one we will say
that a real function is computable in E n if it can be approximated by a
series of rationals with a functional in E n , and we will say that an integer
function is in an analog class if some extension of it to the reals is. We will
now show that Gn xed k > 2, corresponds to the nth level
of the Grzegorczyk hierarchy in the same way that corresponds to
the elementary functions.
Proposition 5.4. The following correspondences exist between Gn
and the levels of the Grzegorczyk hierarchy, E n for all n  3:
1.Any function in Gn is computable in E n .
is an extension to the reals of some ~
f on N, then ~
3.Conversely, if f 2 E n then some extension of it to the reals is in Gn+ k .
Proof. To prove that functions in Gn can be computed with functionals
in E n , we follow the proof of Proposition 4.4 for composition and
linear integration. However, when we use Euler's method for numerical
integration, we now apply the bound of Proposition 5.3 and set m, n and
N to grow as AE [d]
for a certain d. Since this is in E n , so are the
functionals  and . Numerical integration of functions in Gn dened
by Equation (15) can also be done in E n , although the numerical techniques
involved are slightly dierent since ~y 0 is dened implicitly. Now, as
in Corollary 4.5, if f takes integer values on the integers we just have to
approximate it to within an error less than 1=2, so the restriction of f to
the integers is in E n .
Conversely, the remarks above show that Gn contains an extension
to the reals of En 1 , and Lemma 4.6 shows that it contains the other initial
functions of E n as well. Furthermore, it is closed under bounded sum and
bounded product for integer-valued functions. The proof of Lemma 4.7
proceeds as before, except that using Proposition 5.3 again, () is now
an extension of this to the reals can be dened in Gn+ k ,
so can the linear dierential equation (7). We showed that Gn contains
extensions to the reals of all initial functions of E n and is closed under
composition and bounded sums and products for integer valued functions.
Therefore, contains extensions to the reals of all functions in E n .
A few remarks are in order. First, we stress that the analog model we
dene contains exactly the nth level of the Grzegorczyk hierarchy if it is
allowed to solve up to n 3 non-linear dierential equations of the form of
Equation (15) and no other non-linear dierential equations.
Secondly, notice that since [nE implies that
Corollary 5.5. Any function in [n (Gn computable in PR and
all primitive recursive functions are contained in [n (Gn
Finally, instead of allowing our model to solve Equation (15), we can keep
everything linear and dene Gn by adding a new basic function which
is an extension to the reals of En 1 . While this produces a smaller set of
functions on R, it produces extensions to R of the same set of functions on
N as the class dened here.
6. CONCLUSION
We have dened a new version of Shannon's General Purpose Analog
Computer in which the integration operator is restricted in a natural way |
to solving linear dierential equations. When we add the ability to measure
inequalities in a dierentiable way, the resulting system L+ k corresponds
exactly to the elementary functions E . Furthermore, we have dened a
hierarchy of analog classes Gn by allowing n 3 non-linear equations
of a certain form, and we have shown that this hierarchy corresponds, level
by level, to the Grzegorczyk hierarchy E n for n  3. When combined with
the earlier result [CMC00] that G contains the primitive recursive
functions, this suggests that subclasses of the primitive recursive functions
correspond nicely to natural subclasses of analog computers.
Several open questions suggest themselves:
1. We used a very specic kind of non-linear operator to dene the classes
in Section 5. Is there a more natural family of non-linear dierential
equations, whose solutions are total functions, which yield non elementary
2. Can we do without  in the denition of L+  k ? Note that we do not
need to include it in the denition of Gn since we can dene
limited integration as
linear integration as
and nally set However, we have been unable to nd a way
to dene  from linear integration alone.
3. Is L closed under bounded product for real-valued functions,
and not just integer-valued ones? We think this is unlikely, since it would
require some form of iteration like that in Equation 15 where y 1 and y 2
converge to the desired values exactly. We see no way to do this without
highly non-linear terms. If L+  k is not closed under real-valued bounded
products then we could ask what class would result from that additional
operation. While the set of integer functions which have real extensions in
the class would remain the same, the set of functions on the reals would be
larger.
4. By adding to our basis a function that grows faster than any primitive
recursive function, such as the Ackermann function, we can obtain transnite
levels of the extended Grzegorczyk hierarchy [Ros84]. It would be
interesting to nd natural analog operators that can generate such functions

5. How robust are these systems in the presence of noise? Since it is
based on linear dierential equations, L may exhibit a fair amount
of robustness to perturbations. We hope to quantify this, and explore
whether this makes these models more robust than other continuous-time
analog models, which are highly non-linear.
6. Our results on the Grzegorczyk hierarchy seem to be somehow related
to [Gak99], which framework is the BSS model of computation. In [Gak99]
the recursive characterization of the BSS-computable functions [BSS89] is
restricted to match the recursive denition of the classes E n . This might
suggest that our continuous-time operations on real functions, namely the
various forms of integration we consider, are related to certain restricted
types of BSS-machines.
It is interesting that linear integration alone, in the presence of  k , gives
extensions to the reals of all elementary functions, since these are all the
functions that can be computed by any practically conceivable digital de-
vice. In terms of dynamical systems, L corresponds to cascades of
nite depth, each level of which depends linearly on its own variables and
the output of the level before it. We nd it surprising that such systems,
as opposed to highly non-linear ones, have so much computational power.
Finally, we note that while including  k as an oracle makes these functions
non-analytic, by increasing k they can be made as smooth as we like.
Therefore, we claim that these are acceptable models of real physical phe-
3nomena, and may be more realistic in certain cases than either discrete or
hybrid systems.

ACKNOWLEDGMENTS

We thank Jean-Sylvestre Gakwaya, Norman Danner, Robert Israel, Kathleen Mer-
rill, Spootie Moore, Bernard Moret, and Molly Rose for helpful discussions, and the
anonymous referees for important suggestions for improvement. This work was partially
supported by FCT PRAXIS XXI/BD/18304/98 and FLAD 754/98. M.L.C. and J.F.C.
also thank the Santa Fe Institute, for hosting visits that made this work possible, and
LabMAC (Laboratorio Modelos e Arquitecturas Computacionais da FCUL).



--R

Equations Di
Achilles and the tortoise climbing up the hyper-arithmetical hierar- chy

Universal computation and other capabilities of hybrid and continuous dynamical systems.
On a theory of computation and complexity over the real numbers: NP-completness

Computational models and function algebras.

An Introduction to Recursive Function Theory.
Cambridge University Press
Extensions de la Hi
Some classes of recursive functions.
Computable functionals.
On the de
Ordinary Di
Matrix Analysis.
Complexity of primitive recursion.


Complexity Theory of Real Functions.
Extension de la notion de fonction r

Real number models under various sets of operations.
Unpredictability and undecidability in dynamical systems.
Recursion theory on the reals and continuous-time computation
Dynamical recognizers: real-time language recognition by analog com- puters
Classical Recursion Theory II.
On the computational power of continuous time neural networks.

A survey of continuous-time computation theory
Abtract computability and its relation to the general purpose analog computer.
Computability in Analysis and Physics.
Functions and Hierarchies.
Analog computation with dynamical systems.
Mathematical theory of the di
Neural Netwoks and Analog Computation: Beyond the Turing Limit.
The complexity of analog computation.
Mathematics and Computers in Simulation
Computable Analysis.
Subclasses of computable real functions.
--TR
The complexity of analog computation
Complexity theory of real functions
Universal computation and other capabilities of hybrid and continuous dynamical systems
Recursion theory on the reals and continuous-time computation
Dynamical recognizers
Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy
Analog computation with dynamical systems
Neural networks and analog computation
Computable analysis
Iteration, inequalities, and differentiability in analog computers
Ordinary Differential Equations
U.S. Technological Enthusiasm and British Technological Skepticism in the Age of the Analog Brain
Subclasses of Coputable Real Valued Functions
The Computational Power of Continuous Time Neural Networks

--CTR
Giuseppe Trautteur , Guglielmo Tamburrini, A note on discreteness and virtuality in analog computing, Theoretical Computer Science, v.371 n.1-2, p.106-114, February, 2007
Manuel L. Campagnolo , Kerry Ojakian, The Methods of Approximation and Lifting in Real Computation, Electronic Notes in Theoretical Computer Science (ENTCS), 167, p.387-423, January, 2007
Jerzy Mycka , Jos Flix Costa, Real recursive functions and their hierarchy, Journal of Complexity, v.20 n.6, p.835-857, December 2004
Daniel Silva Graa , Jos Flix Costa, Analog computers and recursive functions over the reals, Journal of Complexity, v.19 n.5, p.644-664, October
Jerzy Mycka , Jos Flix Costa, The P  NP conjecture in the context of real and complex analysis, Journal of Complexity, v.22 n.2, p.287-303, April 2006
John V. Tucker , Jeffery I. Zucker, Computability of analog networks, Theoretical Computer Science, v.371 n.1-2, p.115-146, February, 2007
Manuel Lameiras Campagnolo, Continuous-time computation with restricted integration capabilities, Theoretical Computer Science, v.317 n.1-3, p.147-165, June 4, 2004
Jerzy Mycka , Jos Flix Costa, A new conceptual framework for analog computation, Theoretical Computer Science, v.374 n.1-3, p.277-290, April, 2007
Olivier Bournez , Emmanuel Hainry, Recursive Analysis Characterized as a Class of Real Recursive Functions, Fundamenta Informaticae, v.74 n.4, p.409-433, December 2006
Olivier Bournez , Emmanuel Hainry, Elementarily computable functions over the real numbers and R-sub-recursive functions, Theoretical Computer Science, v.348 n.2, p.130-147, 8 December 2005
elementary functions;dynamical systems;subrecursive functions;recursion theory;analog computation;primitive recursive functions;grzegorczyk hierarchy;differential equations