Applied Mathematics and Computation 178 (2006) 103–117

www.elsevier.com/locate/amc

Analog computation beyond the Turing limit

Jerzy Mycka
Institute of Mathematics, University of Maria Curie-Sklodowska, pl M. Curie-Sklodowskiej 1, 20-031 Lublin, Poland

Abstract

The main purpose of this paper is quite uncontroversial. First, we recall some models of analog computations (including
these allowed to perform Turing uncomputable tasks). Second, we support the suggestions that such hypercomputable
capabilities of such systems can be explained by the use of infinite limits. Additionally, the inner restrictions of analog
models of computations are indicated.
 2005 Elsevier Inc. All rights reserved.

1. Preliminaries

Alan Turing clarified the notion of algorithm giving it a precise meaning as well as introduced a coherent
framework for discrete computation. Soon, new results showing the relations of his model with other
approaches, such as recursive functions (in the sense of Kleene) or ChurchÕs k-calculus (for information about
this subject, see Odifreddi [21]), originated in a natural way consistent theoretical basis to standard computa-
tion theory. However, all these models use enumerable domains and treat time of computations as discrete.
Nevertheless, computers need not have such qualities. Analog computers with the continuous internal
states rather than discrete, as in digital computation, were invented and discussed quite thoroughly. Unfortu-
nately, because of the problem of a coherent theoretical basis for analog computation and the fact that analog
computers technology improved insignificantly in the second half of the last century, when compared with its
digital counterpart, analog computation was about to be forgotten. For many reasons (new paradigms of
computation, search for good tools for numerical analysis, new technologies) this situation seems to change.
We may classify analog models as discrete time models (e.g., [1]) or as continuous time models. In this
paper we are interested in the latter type. The basic model in this field is ShannonÕs General Purpose Analog
Computer [29]. The General Purpose Analog Computer (GPAC) is a computer whose computation evolves in
continuous time. The outputs are generated from the inputs by means of dependences defined by a finite direc-
ted graph (not necessarily acyclic) where each node is one of the following boxes.

• Integrator: a two-input, one-output unit with a setting forRinitial condition. If the inputs are unary functions
t
u, v, then the output is the Riemann–Stieltjes integral kt  t0 uðxÞ dvðxÞ þ a, where a and t0 are real constants
defined by the initial settings of the integrator.

E-mail address: Jerzy.Mycka@umcs.lublin.pl

0096-3003/$ - see front matter  2005 Elsevier Inc. All rights reserved.
doi:10.1016/j.amc.2005.09.074
104 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117

• Constant multiplier: a one-input, one-output unit associated to a real number. If u is the input of a constant
multiplier associated to the real number k, then the output is ku.
• Adder: a two-input, one-output unit. If u and v are the inputs, then the output is u + v.
• Multiplier: a two-input, one-output unit. If u and v are the inputs, then the output is uv.
• Constant function: a zero-input, one-output unit. The value of the output is always 1.

A real constant multiplier unit An adder unit

associated to the value k

A multiplier unit A constant function unit

A nintegrator unit
Representations of different types of units in a GPAC.

Although the above notion of GPAC seems fairly intuitive and natural, the accepted definition is due to
Pour-El (see [23]). Let us now present a precise version of her definition for functions of one variable. In
the following, I will denote a closed bounded interval with non-empty interior.

Definition 1 [23]. The unary function y is generated by a GPAC on I if there exist a set of unary functions
y1, . . . , yn and a set of initial conditions y i ðaÞ ¼ y i ; i ¼ 1; . . . ; n, where a 2 I, such that,

1. y ¼ ðy 1 ; . . . ; y n Þ is the unique solution on I of a system of ODEs of the form

dy
Aðx; y Þ ¼ bðx; y Þ ð1Þ
dx
satisfying the initial conditions, where Aðx; y Þ and bðx; y Þ are n · n and n · 1 matrices, respectively. Further-
more, each entry of A and b must be linear in 1, x, y1, . . . , yn.
2. For some 1 6 i 6 n, y = yi on I.
3. ða; y 1 ; . . . ; y n Þ has a domain of generation with respect to the above equation, i.e., there are closed intervals
J0, J1, . . . , Jn (with non-empty interiors) such that ða; y 1 ; . . . ; y n Þ is an interior point of J0 · J1 ·    · Jn and,
furthermore, whenever ðb; z1 ; . . . ; zn Þ 2 J 0  J 1      J n , there exist unary functions z1, . . . , zn such that,
(i) zi ðbÞ ¼ zi for i = 1, . . . , n;
(ii) (z1, . . . , zn) satisfy Eq. (1) on some interval I* with non-empty interior such that b 2 I*;
(iii) (z1, . . . , zn) is unique on I*.

The existence of a domain of generation indicates that the solution of the above equation remains unique
for sufficiently small changes on the initial conditions.
Let us recall that a function f(x) is differentially algebraic [25] if its derivatives satisfy a polynomial equation
P(x, f (x), . . . , f (k)(x)) = 0 for some polynomial with rational coefficients. A function of several variables is
differentially algebraic if it is a differentially algebraic function of each variable when the others are fixed.
Provided with the above definition, Pour-El shows the following result.

Theorem 2 [23]. If y is generable on I by a GPAC, then there is a closed subinterval I 0  I with non-empty
interior such that on I 0 , y is differentially algebraic.
 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117 105

Another important model of analog computation is RubelÕs Extended Analog Computer (EAC) [27]. This
model is similar to the GPAC, but we allow other types of units and several independent variables because
Rubel does not seek any equivalence with existing models. The EAC permits all the operations of ordinary
analysis, except the unrestricted taking of limits. The new units add an extended computational power rela-
tively to the GPAC.
The EAC works on a hierarchy of levels, getting more versatile as one goes to higher levels in the hierarchy.
At the lowest level 0, it produces and manipulates real polynomials of any finite number of real variables. The
EAC has no inputs from outside, but it has a finite number of settings (arbitrary real numbers). The settings
determine behavior of the machine from the first level through all subsequent levels. The EAC has outputs and
we demand them to be real analytic. The outputs at level n  1 can be used as inputs at level n. The EAC sat-
isfied the condition that when inputs at some level are modified by small errors then the outputs differ from the
original output only by a small amount on each compact set.
At each level, the actual computing is done by some boxes of different kinds. First, there are the constant
boxes, which produce arbitrary real constants. There are projection boxes, which produce any of variables
x1, . . . , xn. Later, there are adders, multipliers and substituters (for given v, u1, . . . , uk they give v(u1, . . . , uk) as
the output). Moreover, there are inverters, which for given f1 ; . . . ; fk : Rnþk ! R find real analytic functions
y1, . . . , yk of x1, . . . , xn such that for all 1 6 i 6 k we have fi(x1, . . . , xn, y1, . . . , yk) = 0. We have differentiators,
that for any function produce desirable mixed derivatives. Certain sets in Euclidean space are produced by the
machine for a given function f, namely {(x1, . . . , xn) : f(x1, . . . , xn) > 0} or {(x1, . . . , xn) : f(x1, . . . , xn) P 0}. Then
there are the analytic continuation boxes, which produce a unique analytic continuation for given function and
domain.
The quintessential box is the boundary-value problem box, which solves a finite set of partial and ordinal
differential equations on the given set with certain bound and boundary values prescribed. For some given
function f and set X with the given boundary we can also use restricted limit box, which defines /
(x) = limy!x,y2Xf(y).
Using the results from [25,27] we can formulate the following statement.
Proposition 3 [27]. The set of GPAC-computable functions is a proper subset of the set of EAC-computable
functions.
For example, the EAC can generate the C- and f-functions (it is known that the GPAC cannot solve these
problems [25]). It is not known if a physical version of the EAC exists.
A new approach was given by Moore in 1996. In the work [13], he defined a set of (vector-valued) functions
on the reals (called R-recursive functions) in the analogous way to the classical recursive functions on the nat-
ural numbers. His model has also a continuous time of computation (a continuous integration instead of a
discrete recursion). MooreÕs seminal paper gave rise to a further development in real recursive function theory
(in spite of some problems with his definition and results).
In [18] one can find the definition, which is a derivative of MooreÕs original formulation, introduced to
avoid problems involved in the latter. It is important to see that the following definition is based on the vector
operations.
Definition 4 [18]. The set of real recursive vectors is generated from the real recursive scalars 0, 1, 1 and the
real recursive projections I in ðx1 ; . . . ; xn Þ ¼ xi ; 1 6 i 6 n; n > 0, by the operators:

1. Composition: if f is a real recursive vector with n k-ary components and g is a real recursive vector with
k m-ary components, then the vector with n m-ary components (1 6 i 6 n)
kx1 . . . xm  fi ðg1 ðx1 ; . . . ; xm Þ; . . . ; gk ðx1 ; . . . ; xm ÞÞ
is real recursive.
2. Differential recursion: if f is a real recursive vector with n k-ary components and g is a real recursive vector
with n (k + n + 1)-ary components, then the vector h of n (k + 1)-ary components, which is the solution of
the Cauchy problem for 1 6 i 6 n
hi ðx1 ; . . . ; xk ; 0Þ ¼ fi ðx1 ; . . . ; xk Þ;
106 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117

oy hi ðx1 ; . . . ; xk ; yÞ ¼ gi ðx1 ; . . . ; xk ; y; h1 ðx1 ; . . . ; xk ; yÞ; . . . ; hn ðx1 ; . . . ; xk ; yÞÞ

is real recursive whenever h is of the class C1 on the largest interval containing 0 in which a unique solution
exists.
3. Infinite limits: if f is a real recursive vector with n (k + 1)-ary components, then the vectors h, h 0 , h00 with n k-
ary components (1 6 i 6 n)

hi ðx1 ; . . . ; xk Þ ¼ lim fi ðx1 ; . . . ; xk ; yÞ;

y!1

h0i ðx1 ; . . . ; xk Þ ¼ lim inf fi ðx1 ; . . . ; xk ; yÞ;

y!1

h00i ðx1 ; . . . ; xk Þ ¼ lim sup fi ðx1 ; . . . ; xk ; yÞ;

y!1

are real recursive in the domain containing these points, where these limits exist for all 1 6 i 6 n.
4. Arbitrary real recursive vectors can be defined by assembling scalar real recursive components.
5. If f is a real recursive vector, then each of its components is a real recursive scalar.

From the physical point of view with such a definition we are ready to use only a finite amount of energy.
The possibility of operations on undefined functions is excluded here: our functions are strict in the sense that
for undefined arguments they are also undefined. But to obtain some interesting functions we should improve
the power of this system by the use of the operators of infinite limits. Let us point out that introducing of infi-
nite limits gives discontinuous functions. We should also remember that in some cases we can use limits in
some real point. This is possible by transforming them into infinite limits. For example, limy!p2 sin xy can be
written as limy!1 sin x(arctan y).
To illustrate further this transformation let us point out that if f is a (n + 1)-ary real recursive function, then
its derivative oy f ðx1 ; . . . ; xn ; yÞ ¼ limx!1 xðf ðx1 ; . . . ; xn ; y þ x1 Þ  f ðx1 ; . . . ; xn ; yÞÞ is a real recursive function,
whenever such a limit exists. For example, if we take ky Æ 1/y then limx!1 ð1=ðy þ x1 Þ  1=yÞx ¼
limx!1 xðy  y  x1 Þ=½ðy þ x1 Þy ¼ 1=y 2 is a real recursive function. Derivatives are physically realizable: the
class of differential algebraic functions is closed under derivatives, making a large class of derivatives physi-
cally realizable.

2. Properties of analog computation by means of real recursive functions

Now we can consider a new problem. Are there different levels of difficulty in a computation if it goes in the
analog way? The natural measure of a function difficulty can be joined with the degree of (dis)continuity. The
above considerations lead us to the conception of the g-hierarchy which describes the level of nesting limits in
the definition of a given function.
Syntactic descriptions of real recursive vectors are needed to formulate a precise definition. Some kind of
symbols called basics descriptors are introduced for all basic real recursive functions. The combination of such
descriptions for given real recursive functions will form a new description of another function. For basic func-
tions we can propose: ijk is a k-ary description for projection I jk for all 1 6 j 6 k; 1k ; 1k ; 0k are k-ary descriptions
for constants 1, 1, 0 used with k variables. We must also add operator symbols (descriptors) for all intro-
duced operators: dr–for a differential recursion, c—for a composition, l, ls, li—for a respective kind of limits
(lim, limsup, liminf).

Definition 5 [18]. The collection of descriptors of real recursive vectors is inductively defined as follows:

• ijn is a n-ary description of I jn , 1 6 j 6 n 2 N; 1n is a n-ary description of f(x1, . . . , xn) = 1; 1n is a n-ary

description of f(x1, . . . , xn) = 1; 0n is a n-ary description of f(x1, . . . , xn) = 0; for all (x1, . . . , xn) 2 Rn, n 2 N;
• if hhi = hh1, . . . , hmi is a k-ary description of the real recursive vector h and hgi = hg1, . . . , gki is a n-ary
description of the real recursive vector g, then c(hhi, hgi) is a n-ary description of the composition of h
and g;
 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117 107

• if hhi = hh1, . . . , hni is a k-ary description of the real recursive vector h and hgi = hg1, . . . , gni is a (k + n + 1)-
ary description of the real recursive vector g, then dr(hhi, hgi) is a (k + 1)-ary description of the function
defined by differential recursion;
• if hhi = hh1, . . . , hmi is a (n + 1)-ary description of the real recursive vector h, then l(hhi), li(hhi), ls(hhi) is a n-
ary description of an appropriate infinite limit (respectively lim, liminf, limsup) of h;
• if hf1i, . . . , hfmi are n-ary descriptions of real recursive k-ary scalar functions f1, . . . , fm, then v(hf1i, . . . , hfmi) is
a k-ary description of the real recursive vector f = (f1, . . . , fm).

At the moment we can define the g-number for a description of some real recursive function f.

Definition 6 [18]. For a given n-ary description s of a vector function f let Eki ðsÞ (the g-number with respect to
ith variable of the k-component) be defined as follows:

1. E1i ð0n Þ ¼ E1i ð1n Þ ¼ E1i ð

1n Þ ¼ 0;
2. Emi ðcðhhi; hgiÞÞ ¼ max16j6k ðEmj ðhhiÞ þ Eji ðhgj iÞÞ, where h is a n components k-ary vector and g is a k-compo-
nents m-ary vector;
3. for a differential recursion we distinguish two cases:
• i 6 k:

Eji ðdrðhf i; hgiÞÞ ¼ maxðE1i ðhf1 iÞ; . . . ; E1i ðhfn iÞ; E1i ðhg1 iÞ; . . . ; E1i ðhgn iÞ; E1kþ1 ðhg1 iÞ; . . . ; E1kþ1 ðhgn iÞÞ.

• i = k + 1:

Eji ðdrðhf i; hgiÞÞ ¼ max ðmaxðE1kþmþ1 ðhg1 iÞ; . . . ; E1kþmþ1 ðhgn iÞÞÞ;
06m6n

where f is a n components k-ary vector and g is a n components (k + n + 1)-ary vector;

4. Eki ðlðhhiÞÞ ¼ Eki ðliðhhiÞÞ ¼ Eki ðlsðhhiÞÞ ¼ maxðEki ðhhiÞ; Eknþ1 ðhhiÞÞ þ 1, where h is a k components (n + 1)-ary
vector.

The main idea of the above definition is to count nested limits in descriptions. In point (3) we should dis-
tinguish the case i = k + 1 (differential recursion is given with respect to this variable); in this case hfi is not
important for the counting.
For the n-ary description s of m components we can define now EðhhiÞ ¼ maxk maxi Eki ðhhiÞ for 1 6 i 6 n,
1 6 k 6 m. Now we can deal with the g-number for a real recursive function.

Definition 7 [18]. For a given real recursive function f, let g(f) be defined as the minimum of E(hfi) for all
possible descriptions of the function f.
We are ready to conclude with the definition of the g-hierarchy as a family of Hj = {f : g(f) 6 j}. It will be
comfortable to think about the g-hierarchy as a measure of the difficulty of real recursive functions. If f 2 Hj,
then j nested limits is used to define f. However we can patch functions defined by infinite limits, so j can be
seen as the number of nested (non-parallel) g needed to patch the function f to the total function. Hence, as
another equivalent definition we can suggest the following: if f is a real recursive function, then E(f) = j if at
most j nested g operations are necessary to create ftotal such that ftotal is everywhere defined and if f ðx0 Þ is
defined, then ftotal ðx0 Þ ¼ f ðx0 Þ.
Let us illustrate the above part of the text with some examples.

Example 8. The functions +, ·, , exp, sin, cos, kx  1x, /, ln, kxy Æ xy are real recursive functions from H0. The
Kronecker d-function, the signum function, absolute value, the Heaviside function H, the binary maximum
max, the square-wave function s and the floor function are in H1.
Let us give the examples of some functions which are significant in mathematics and can be expressed in
terms of real recursiveness.
108 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117

Example 9. The Bessel functions of the first kind Jv of order v (integer) are real recursive functions of the class
H0. The EulerÕs C-function and the Riemann f-function are real recursive functions from the class H1.
R1
Let Rus0 comment briefly Euler function: CðxÞ ¼ 0 tx1 expðtÞ dt. It is simple R s0 to observe CðxÞ ¼
s
lims0 !1 0 sx1 expðsÞ ds. Because sx1exp(s) is a real recursive function and 0 sx1 expðsÞ ds is in H0
hence C is in H1.
Proposition 10 [18]. The class of real recursive functions is a proper superset of the class of GPAC-computable
functions.
The above proposition is obvious considering our results that C Euler function and f Riemann function are
real recursive functions and the result of Marion Pour-El [23] that these functions are not GPAC-computable.
For the proper analysis of functions it is important to control the domain and singularities of functions. We
can postulate new operators which may check the points: are they in the domain of some functions or not.
Definition 11 [18]. For any function f : Rnþ1 ! R let
1 if lim f ðx; yÞ exists;
(
y!1
gy f ðx; yÞ ¼
0 otherwise.
The definitions of giy and gsy are given by a replacement of lim by liminf and limsup, respectively, in the above
equation.
Defined in this way gy f ðx; yÞ is a characteristic function for the set of such x that limy!1 f ðx; yÞ is well
defined1 (without singularities). Analogously, giy f ðx; yÞ, gsy f ðx; yÞ play the same role, respectively, for
lim inf y!1 f ðx; yÞ, lim supy!1 f ðx; yÞ. The problem arises whether such operators are real recursive operators.
If the answer to this question is ÔyesÕ, we may patch any partial function to a total one. For example, let the
function f be total and F total ðxÞ ¼ limy!1 ðgy f ðx; yÞÞf ðx; yÞ, F ðxÞ ¼ limy!1 f ðx; yÞ. The function F total ðxÞ is total
and has such a property that if F ðxÞ is defined, then F total ðxÞ ¼ F ðxÞ. For points which are not in the domain of
F we have F total ðxÞ ¼ 0.
Proposition 12 [18]. The functions gy g, giy g, gsy g are total real recursive functions if g is a total real recursive
function.
Now we can turn to some application of the g-operator. We consider a possibility of a process of Turing
machines simulation by real recursive functions.
Let us consider a Turing machine given by the following description. It consists of an infinite tape for stor-
ing the input, output, and scratch working, and a finite set of internal states. All elements on a tape are strings.
Without any loss of generality, we can choose some alphabet for these strings, the binary alphabet is a prac-
tical choice. The machine works in steps. At one step it scans the symbol from the current position of the tape
(under the head of the machine), changes this symbol according to the current state of the machine and moves
the position of the tape to the left or right with a transformation of state. Some states are distinguished as
final, when the machine reaches one of them, then it stops. Our Turing machine model obeys to the classical
constraints: (a) input is finite and (b) output is finite, regardless of the computation length.
Proposition 13. There are real recursive functions from the class H1, which can simulate any Turing machine,
i.e., for a machine M there exists a real recursive function fM : R2 ! R2 such that for the initial tape and state
encoded into (x, y) the nth iteration fMn ðx; yÞ gives the codes of the tape and state after n steps of Turing machine.
It can be mentioned that the process of simulation is especially important for universal Turing machines.
The results in this area proved last year (e.g., [24]), give us the interesting restrictions of the size of such
machines (for example, there exists a universal Turing machine for 5 states and 5 symbols) which leads us
to a significant simplicity of the constructed function. It is worth pointing out that fM can be analytical
(see [10]).

1
Whenever we say that lim, limsup, liminf are defined, we want to say that they belong to R.
 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117 109

Let us signal a few important questions concerning Turing machines. The first problem is known as the
halting problem: does the machine M for input (x, y) reach the final state? There is not a natural recursive
characteristic function of this problem. The method of simulation of Turing machines given above can resolve
it in the simple way with real recursive functions.
Proposition 14 [18]. For any Turing machine M, there exists a real recursive function which is the characteristic
function of the halting problem for M.
bzc
Proof. We can define F 0M ðx; y; zÞ ¼ fM ðx; yÞ, then let

H M ðx; yÞ ¼ ðgz F 0M ðx; y; zÞÞAðlim ðgz F 0M ðx; y; zÞÞ  F 0M ðx; y; zÞÞ;

z!1

where
P A(x, y) = 1 if the state written in x is final (accepting), 0 otherwise. The function A(x, y) can be defined
Pm1
as s2F a¼0 hðmþ1Þn ðx  s  naÞ. The function HM is a real recursive characteristic function of the halting
problem for the machine M. h
To obtain the function computed by M, it is enough to iterate the steps up to reaching the final state by the
machine. If the machine M ends in the final state for some tape (x, y), then there exists such n0 2 N that the
sequence fMn ðx; yÞ is constant for n P n0. We can define the function FM(x, y) computable by M as
bzc
F M ðx; yÞ ¼ lim ½fM ðx; yÞ  gðAðlim ðgz F 0M ðx; y; zÞÞ  F 0M ðx; y; zÞÞÞ;
z!1 z!1

1
where g is a function not defined at 0, otherwise it takes value 1 (for example given as limy!1 1expðjxjyÞ ). Then
FM is defined whenever lim exists and the value of the function A is 1 (i.e., the Turing machine M reaches for
the initial tape (x, y) the final state), otherwise is undefined.
Let us turn for a moment into the problems of computation beyond the power of Turing machines. The
problem of infinity, which can appear in the sequel of not finishing computation, introduced problems into
the computability theory and practice. The first step to improve this situation is directed to change the behav-
ior of a Turing machine. For this purpose we may use an accelerated Turing machine [5]. Its description is the
same as for a standard Turing machine, but a temporal pattern of steps is given. Each subsequent step is per-
formed in half the time of the step before. Such machines could complete an infinity of steps in two time units
only. This feature of accelerated Turing machines gives us the power to puzzle out the halting problem by pro-
gramming the following algorithm: mark the first square on the tape by 0, change it only in the final (last) step
to 1, if after 2 time units we have 0 in the distinguished square, then machine does not halt, otherwise it halts.
However, some difficulties arise also in this model. Let us imagine the machine changing value of one square
from 1 to 0 and, conversely, in all steps using only one non-final internal state. We can hesitate what is on the
tape after all steps (in infinity) because in this case the computation diverges. The accelerated Turing machine
can be simulated in the same way as the standard Turing machine with only one modification: in the definition
of FM(x, y) it is not necessary to have the result (zx, zy) with a final state i written in zx. Hence, the convergent
infinite computations and finite computations both give the correct result, however the divergent computa-
tions have an undefined result. As we can observe, real recursive functions are quite a powerful tool of a
description for this problem of infinite computation.
The above remarks prove that g-operator gives us an additional power to standard models of computation
by controlling the domain of computable functions and machines. Such possibility is an effect of checking in a
finite amount of time an infinite number of computation elements.
At this moment we can generalize our considerations from the notion of Turing machine up to a wider
characterization of computability. We will proceed with the relations of natural numbers taken from the arith-
metical hierarchy. The class R00 ¼ P00 contains only such relations which have recursive characteristic func-
tions, i.e., which can be computed by Turing machines. The upper stages of this hierarchy can be
constructed from the lower ones in the following way:
R0nþ1 ¼ fP : ð9P 0 2 P0n ÞP ðmÞ
  9sP 0 ðm;
 sÞg;
P0nþ1 ¼ fP : ð9P 0 2 R0n ÞP ðmÞ
  8sP 0 ðm;
 sÞg;
110 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117

where P  Nk, P 0  Nk+1, k P 1. To complete our hierarchies we can add the following equation D0n ¼
R0n \ P0n ; n P 0.
The importance of the arithmetical hierarchy is connected with many fields. It can be observed as a kind of
formal description of definability (see [21]). Its classes can be used to classify a complexity of mathematical
notions (e.g., the definition of a limit of sequences is of P03 class). From the computability theory point of view
we can see the arithmetical hierarchy as the levels of natural functions (given by their graphs) which are dif-
ferent in quantity of infinite ÔwhileÕ loops necessary to their computation. Also linguistic problems of computer
science can be expressed in terms of this hierarchy. The most known example is the one of the classes of recur-
sive (R00 ) and recursive enumerable (R01 ) languages. In some sense we can also see this hierarchy as a measure of
uncomputability of functions (or undecidability of relations). Especially, the halting problem is known to be
R01 .
We are interested in a correlation of this infinite hierarchy of sets and relations to the g-hierarchy. Going to
infinity with n for the function fMn and using the fact that all recursive sets and relations have Turing comput-
able total characteristics, we get the following conclusion.
Corollary 15 [18]. Every recursive set or relation (with argument from N) is in H2, i.e., R00 ¼ P00 H 2.
For the rest of the arithmetical hierarchy we have the following result.
Theorem 16 [18]. The sets and relations from R0i , P0i belong to Hi+2 for i P 0.
This fact does not mean that a better real recursive restriction for the arithmetical hierarchy does not exist.
Let us analyze one aspect of the analytical hierarchy. This hierarchy exceeds strongly the arithmetical one. We
can deal with especially important class P11 . Let us mention that P11 sets can be uniformized by sets of the same
class. Moreover, for any n 2 N the classes R0n and P0n are subsets of P11 . The class of P11 relations is defined by a
function quantifier used on an arithmetical relation: R 2 Nkþ1 is P11 if Rðx; yÞ  ð8f : N ! NÞQðx; f ðyÞÞ, where
Q is from some level of the arithmetical hierarchy.
Proposition 17. Any relation R 2 P11 is in H6.
The levels of the analytical hierarchy and their relation to the g-hierarchy can be analyzed with the l-oper-
ator like in [13]. Because the l-operator may be replaced by infinite limits (see [15]) the remaining part of the
analytical hierarchy can be obtained in this way.

3. Real functions computable by Turing machines

Let us change our approach. From now on we will use only classical computational devices like Turing
machine. To define real functions computable by such machines we have to consider a way of an approximation
of real numbers by natural ones. This method is well known (e.g., [9]), here we use an approach such as in [34].
Let us present the method of a connection of real computations with Turing machines. The first step is
devoted to some coding of rational number (from Q) into natural numbers. We use Cantor pairing function
hi; ji ¼ ðiþjÞðiþjþ1Þþj
2
and inverses p1(hi, ji) = i, p2(hi, ji) = j. Of course, we can extend this for more arguments:
ij
hi, j, ki = hi, hj, kii. It is possible to define an effective numbering vQ : N ! Q such that vQ ðnÞ ¼ kþ1 , for
n = hi, j, ki. A function f : Nk ! Q is called computable iff f ðn1 ; . . . ; nk Þ ¼ vQ ðgðn1 ; . . . ; nk ÞÞ for some function
g : Nk ! N computable by Turing machine.
The next step is connected with computable sequences of real numbers. A sequence ðxn Þn2N of real numbers
is computable in this sense if there is computable (in the sense of the previous paragraph) double sequence
ðrn;m Þn;m2N of rational numbers which converges uniformly and effectively to ðxn Þn2N , namely there is a Turing
computable function e : N2 ! N such that
ð8n; m; k 2 NÞðk P eðn; mÞÞ ! jrn;k  xn j < 2m .
Let us explain that the above definition can be expressed in such an informal way: the sequence of real num-
bers is computable if there exists such a Turing machine that for the given index n of some element of this
sequence and for the given precision 2m this machine computes the code of such rational number r, which
differs with xn less than 2m.
 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117 111

At the last step we would like to define a real function, which can be approximated by Turing machine. We
want to have the following intuition preserved—if a given rational argument is in the known neighborhood of
x then the Turing machine gives rational number in the known neighborhood of f(x). Moreover, we should
have a possibility to decide by some parameter how small is the neighborhood.
So we would like to have for a function f an effective procedure which uses a Turing machine Mf: for a given
precision n and for a given sequence rm,k (produced by another Turing machine) convergent to x, this proce-
dure finds such m0, k0 that M f ðrm0 ;k0 Þ ¼ q and jq  f(x)j < 2n.
With this intuition we can give the definition of computable real functions, here in the sense of functions
approximable by Turing machines.

Definition 18 [34]. A real function f : ½a; b ! R is called computable, if f maps every computable sequence
ðxn Þn2N of real numbers to a computable sequence ðf ðxn ÞÞn2N and there exists a recursive function d : N ! N
such that
ð8x; y 2 ½a; bÞð8n 2 NÞjx  yj < 2dðnÞ ! jf ðxÞ  f ðyÞj < 2n .
Such definition gives us quite different look at the problem of computability over the reals. Here we restrict
the set of real functions in such a manner, that we consider only functions, which can be approximated effec-
tively by Turing machines. In this sense they are physically computable by digital computers, because we can
always find as the result a rational number near to the original value of a function with any desirable precision.
Such functions cannot be treated as any instance of hypercomputation. Let us point out that e, p are real com-
putable, that means we have a method to a rational number in any neighborhood of them; ChaitinÕs X is not
real computable in this sense.

4. GPAC and H0 versus Turing machines

We introduce a simple concept—by an analogy with the recursive functions of Kleene, whenever a function
is defined only with composition and differential recursion (f 2 H0), we call f a primitive real recursive
function.2
Proposition 19 [18]. Every primitive real recursive function f defined on the closed domain D 2 Rn is GPAC-
computable.
However, let us point out that there are functions (like kx Æ jxj in the interval [1, 1]), which are bounded
with their derivatives but they, or some of their derivatives, are not continuous (and not primitive real recur-
sive ones).
We can observe that the model of analog computation given by real recursive functions includes GPAC-
computable functions.
Theorem 20 [18]. Every GPAC-computable function with real recursive numbers as parameters is a real
recursive function.
Now let us do the first step to analyze when some functions generated by analog computation are beyond
the Turing limits of computations. Of course, real computable functions described in the previous section are
under this limit. But what is the situation of GPAC-computable functions? This question is additionally
important because, as we can observe from the above propositions, GPAC-computable functions form the
basic level of analog computations, which is a common part of EAC-computable functions and real recursive
functions.
The answer can be found in RubelÕs paper [26], where the following theorem (in the slightly different for-
mulation) is proved.

2
There is a slight difference since (classical) primitive recursive functions are always total and primitive real recursive functions can be
partial.
112 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117

Proposition 21 [26]. For any GPAC with a locally unique solution, which is analytical on an open interval I
containing 0 with an analytical output f, if all the constants are rational numbers, then there is an open subinterval
0 2 J I, on which f is digitally computable.
In [26] the phrase Ôf is digitally computableÕ means that there is a uniform algorithm for producing polyno-
mials pn with rational coefficients such that jpn ðxÞ  f ðxÞj < 1n for all x 2 J. It is simple to observe that this con-
dition can be transformed into conditions satisfied by real computable functions in the sense of Definition 18.
Now, we can consider another important case of analog computation. Let us look closer at the primitive
real recursive functions, i.e., at the class H0. All functions from this class are GPAC-computable by Proposi-
tion 19. From these results we have a corollary that all primitive real recursive functions are real computable.
We can also obtain the same result by the following observation. The basic functions (constants and projec-
tions) are real computable. Composition of two real computable functions is also real computable. Hence, the
only one not obvious case is a definition by differential recursion. However, an integration used by this oper-
ator can be approximated by some kind of numerical integration with a control of a precision, which gives us a
real computable solution. So, we have the corollary.
Corollary 22. Every primitive real recursive function can be approximated by Turing machines.
The above results teach us that analog computation in some cases does not increase the computational power
beyond Turing border. This is not sufficient (as it is sometimes suggested) to use real numbers to cross restric-
tions of Turing computability. Of course, the precise comparison of Turing and analog computability depends
on a detailed analysis of all operations allowed in the discussed models.

5. What can us take beyond the Turing limit?

Let us try to enumerate some examples of hypercomputational properties of analog computation and to
find the common elements.
Moore in his paper [13] proves the theorem that the halting problem is solvable by R-recursive functions
if we allow to use the zero-finding l-operator. However, we can avoid the use of this, somehow unnatural
for the analog world of mathematical analysis, operator. The good choice seems to be guaranteed by infinite
limits.
Theorem 23 [15]. If f ðx; yÞ : Rnþ1 ! R is a real recursive function then the function g : Rn ! R, gðxÞ ¼
ly f ðx; yÞ is real recursive too.
Hence, we obtain a corollary that the halting problem can be solved by real recursive functions, when we
use infinite limits in the solution. The same fact, by a different method, is given in our Proposition 14.
Let us discuss briefly another analog device. It is an open problem whether EAC can be simulated by Tur-
ing machines (in general, by digital computers). However, this is a known fact that EAC is stronger that
GPAC and it can compute some difficult functions (e.g., C-function, f-function). We can observe that these
properties are connected with infinite limits, namely the proofs of EAC-computability for such functions
use the mentioned operation. It would suggest that the power of EAC is strongly connected with limits incor-
porated in its structure.
In the classical framework we can create uncomputable functions (relations) extending the set of Turing
computable functions to the whole arithmetical hierarchy. As a consequence of the definition of this hierarchy
we find unrestricted quantifiers as tools leading toward uncomputability. Hence, we need to analyze the
method of quantifiers usage.
For every function f : Rn+1 ! R we can construct such a real recursive function qf : Rn ! R that
1 9y 2 Nf ðx; yÞ ¼ 0;

qf ðxÞ ¼
0 8y 2 Nf ðx; yÞ 6¼ 0.

To this effect we start with a description of the function fc ðx; yÞ ¼ 1  dðf ðx; yÞÞ. This function has the follow-
ing property fc ðx; yÞ ¼ 1  f ðx; yÞ 6¼ 0, fc ðx; yÞ ¼ 0  f ðx; yÞ ¼ 0. It is easy to observe that now
 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117 113

z
0 9y 2 Nf ðx; yÞ ¼ 0;
Y 
lim fc ðx; jÞ ¼
z!1
j¼0 1 8y 2 Nf ðx; yÞ 6¼ 0.
Qbzc
Hence qf ðxÞ ¼ 1  limz!1 j¼0 fc ðx; jÞ. We should indicate two points. The first: real recursive functions are
closed under the product operation. It can be defined as an iteration of the function tf : Rn+2 ! Rn+2,
tf ðx; y; iÞ ¼ ðx; yf ðx; iÞ; i þ 1Þ, hence
n
Y
f ðx; iÞ ¼ I 23 ðtnf ðx; 1; 0ÞÞ.
i¼0

The second: let us analyze the stage of g-hierarchy which contains qf ðxÞ if f 2 HQi,n where i 2 N is a given num-
ber. The function fc is in Hi+1 and consequently by properties of an iteration j¼0 fc ðx; jÞ 2 H iþ1 . Finally, we
can claim that qf 2 Hi+2.
The same method is applicable to the general quantifier. In this way we can, once more, conclude that an
uncomputable character of natural functions and relations given by quantifiers appear in the context which
can be explained by real recursive functions with infinite limits.
We can go back for a moment to accelerated Turing machines. It is a well-known fact that such machines
could solve the halting problem. But, as we explained in the previous section, this possibility arises from the
property of reaching infinite number of steps in finite time—this means that hypercomputable properties of
accelerated Turing machines flow from infinite limits, too.
In the light of the above considerations hypercomputation for analog devices has a strong connection with
infinite limits. The use of infinite limits gives a possibility of an analysis for infinite number of cases in finite
amount of resources (time, space, energy). Therefore, at this stage of our work we can present the uncontro-
versial thesis: with infinite limits some hypercomputational properties are added to analog models of
computation.

6. Are limits physically possible?

From the previous considerations we can deduce that for establishing the boundaries of practically realized
models of computability, the nature of the material world becomes essential. It is important, however, to
become aware of an obvious fact that we do not possess a direct knowledge of this quality of the Universe.
That is why an analysis of its features and limits always takes place by means of physical theories. These the-
ories become the only way to perceive quantitative relations that occur in the physical world.
Therefore, we face the next boundary of our analysis. We cannot discuss ultimate boundaries of comput-
ability but the limits of computability possibilities that result from a physical theory which is regarded as
given. However, it may appear that such a far-reaching claim, namely the postulate of realizing infinity
(energy, time) in some finite sector of physical reality is not acceptable to every physical theory.
The fact that physical reality models does not exhibit super-Turing capabilities is claimed, for example, by
Penrose. In [22] he stresses this point before he talks about the (non-computable) ultimate physical theory and
the human mind: Now, where do we stand with regard to computability in classical theory? It is reasonable to
guess that, with general relativity, the situation is not significantly different from that of special relativity—over
and above the differences in causality and determinism that I have just been presenting. Where the future behavior
of the physical system is determined from initial data, then this future behavior would seem (by similar reasoning
to that I presented in the case of Newtonian theory) also to be computably determined by that data (apart from
unhelpful type of non-computability encountered by Pour-El and Richards for the wave equation, as considered
above—and which does not occur for smoothly varying data). Indeed, it is hard to see that in any of the physical
theories that I have been discussing so far there can be any significant ‘‘non-computable’’ elements.
But it occurs, though, that the above assumptions are not obvious. For more rigor we can restrict the con-
siderations at least to commonly approved (not particularly exotic) physical theories. Two examples of phys-
ical theories which can be seen as allowing hypercomputability will be presented at this moment.
The first is Newtonian mechanics. In 19th century P. Painlevé together with H. Poincaré proposed a par-
ticular analysis of a problem connected with the mechanics of heavenly bodies, that is the question of n-bodies.
114 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117

In this system of n-bodies a solution of an equation system of movements for n gravitational interacting bodies
is sought. P. Painlevé and H. Poincaré opened a discussion not about the way to discover a particular solution,
but about an analysis of qualities of these solutions. There is a crucial question whether there may exist such
solutions that contain a singularity. It is obvious that a situation of this kind happens when two, from all the
described by the problem, bodies collide. Yet, the question arises whether the singularity may appear without
any collision. The answer to this question was given by Xia [33] in 1992. He claimed that for a problem of five
bodies in the three-dimensional space there exist non-collision solutions. The Xia answer causes throwing one
of the bodies to infinity in finite time. As it can be seen, Newtonian mechanics allows finite realizations of
infinity and potentially supports a possibility of calculations exceeding the limits of the Turing machine.
Hence, we have reasons to believe that the n-body dynamics has hypercomputation capabilities and it is
possible to explore them. XiaÕs paper [33] showing that an infinite number of mechanical events can happen
in finite time opens a way of thought. There is an open way to translate the halting problem into the n-body
problem in classical mechanics: it is necessary to show that the subset of initial data that go off to infinity in
finite time codes a universal machine. In TiplerÕs book [32], he conjectured that universal initial data exists and
it seems that the universal initial data is of measure zero in the space of all initial data.
An obvious aim that appears at this moment is relating similar considerations to the physical theories that
are regarded as currently valid (not as Newtonian mechanics). For this purpose we will use the theory of gen-
eral relativity. There are such solutions of EinsteinÔs equations in which there exist a time-like half-curve c as
well as a point p in spacetime such that the entire stretch c is contained in the chronological past of p. Such
spacetime structures (i.e., anti-de Sitter spacetimes) have been examined by physics with pointing out possible
material systems that fulfill the required qualities (compare [8]). Moreover, the descriptions of the usage of
such systems to create computing systems [28] have been proposed. Summing up, this theory, allows conduct-
ing an infinite number of operations in finite time of an appropriate observer.
From the point of view of analog computation, time is very important ingredient of such systems. Hence,
the next element of this discussion will be devoted to a properties of time. Is time a continuous object or rather
a discrete one? In our analog models it seems to be natural way of thinking, that variables (at least one of
them) change in a continuous way in the time dimension of the Universe. This point is under discussion among
experts. Some of them reject the continuous nature of time, others (see for example Newton-Smith in [20])
claim that on empirical grounds, continuous time is a better model for our Universe than discrete one.
The above results do not entitle us to accept the thesis that hypercomputability is possible in our world.
They show, however, that the possibility of crossing the Turing machine barriers is, in the light of some phys-
ical theories, real.
As we have observed, a new cognitive situation is introduced. The boundaries of computability become
valid only for a stated physical theory. Moreover, they receive provisional and temporary character. When
a physical theory regarded as the proper description of the Universe changes, there may occur a change in
computability boundaries. The theory of computability gained additionally a relative character, this time in
relation towards the physical theory assumed as a starting point in a construction of computing systems.

7. Inner restrictions of analog computation with limits

The previous parts of the paper can be seen as a claim that with a use of analog paradigm in computation
equipped with limits we create a framework where all problems are solvable. Such result would be, of course,
disappointing. An omnipotent system of computation would lose its constructive and algorithmic character. If
all analytical functions (or moreover set-theoretical functions) would be computable, then a real meaning of
computation would disappear.
Because the system of real recursive functions was presented as very general, let us concentrate on it. Hence,
here by undecidable problems we understand such problems which cannot be solved by real recursive func-
tions. It may be observed, from the below results, that many important problems remain undecidable in this
sense.

Proposition 24 [17]. The problem of domain for real recursive functions is undecidable.
 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117 115

Proposition 25 [17]. The problem of identity of two real recursive functions given by their descriptions (coded
into natural numbers) is undecidable by a real recursive function.
We will say that a description is elegant if it has the property that no smaller description exists. We should
then look at the size of descriptions, and, since they are written in characters, we can size them in quite dif-
ferent ways. As with ChaitinÕs elegant LISP programs (e.g., [4]) we cannot prove that a description is elegant.
Let us assume some computable linear orders into the set of description numbers (i.e., into N). The exam-
ples of such an order can be: m n—the description number m codes a shorter description, or with same
length but occurring lexicographically before the description of code n; m l n—the order is lexicographical
among the set of descriptions; m s n—we compare the number of limits involved in the descriptions of codes
m and n, then the number of differential recursions, then the number of compositions, in the case that all num-
bers are equal we use the length, and later the lexicographical order. All mentioned linear orders are comput-
able, i.e., they can be decided by classical recursive functions, hence by real recursive functions too.

Proposition 26 [17]. The problem of minimal code is undecidable by real recursive functions.
We give a corollary of the above proposition. In the case of the order s some function M counts the min-
imal number of limits needed to define a function given by some description. Since M is not real recursive, we
can conclude that the problem of establishing the minimal level of the g-hierarchy (no matter the number of
differential recursions and compositions) is not decidable in our framework.
On the other side of such problems, we can analyze computability of some numbers. A real recursive
number x is a real recursive function with arity zero (or an equivalent formulation states that there exists a
unary real recursive function f : R ! R with the property f(0) = x). The examples of real recursive numbers
are the integers, but also the rationals, and the algebraic numbers (see [16] for a full proof). Transcendental
1
numbers such R z as p = 4 arctan(1) where arctan(0) = 0, oy arctanðxÞ ¼ 1þx 2 , NapierÕs e = exp(1), EulerÕs
x
c ¼ limz!1 0 e ln x dx, but also ChaitinÕs halting probability X are real recursive in different levels of the
limit hierarchy. However, their number is countable. As analog quantities, these numbers are given once
and for all as entire quantities (see [13]) and not as decimal expansions like in the case of the usual definition
with Turing machines.
A Rice-like general undecidability and incompleteness theorem for real-defined and real-valued functions—
appear in the paper by da Costa and Doria [7], which was submitted for publication in October 1990 and com-
mented by Stewart in Nature (see [31]) in August 1991. Similar results appear in the Ph.D. thesis of Moore
([11, p. 119]) which was submitted to the Math Department in Cornell University in January 1991; those
results had been obtained before December 1990.
Herein we proceed to show how we can adapt the same results (their classical presentation can be found in
[6]), namely RiceÕs theorem, to the set of real recursive functions. We start with the real recursive variant of
another classical result.

Proposition 27 (The analog s–m–n theorem [17]). For each m, n P 1, there is the total real recursive (m + 1) 
mþn
ary function sm
n such that for integer numbers x1, . . . , xm : /e ðx1 ; . . . ; xm ; y 1 ; . . . ; y n Þ ¼ /nsmn ðe;x1 ;...;xm Þ ðy 1 ; . . . ; y n Þ.
This leads us to the well-known and important RiceÕs theorem in the context of analog computation.

Proposition 28 (The analog RiceÕs theorem [17]). Suppose that B is non-empty set of real recursive functions
not coinciding with the whole class. Then the problem kx. ‘‘/x 2 B’’ is undecidable.
In other words, any property that real recursive functions can have, like being injective, or onto, or having
an infinite domain, or having an infinite range, or being total, is undecidable unless it is trivial (corresponding
to the empty set and to the set of all real recursive functions). Now, in terms of dynamical systems, these ques-
tions concern basins of attraction. These basins are in general non-real recursive, i.e., there is no hyper-algo-
rithm that will tell us whether or not a point is in them. In fact, we can even recall Theorem 10 from [12], which
is proved by analog RiceÕs theorem.

Proposition 29 (MooreÕs undecidability theorem [17]). The following questions about continuous-time dynamic
systems are undecidable.
116 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117

1. Given a point x and an open set A, will x fall into A?

2. Given a point x and a periodic point p, will x converge to p? Will a dense set of points converge to p?
3. Is the set of periodic points on a given cylinder infinite? Dense?

We think of a conceptual programming language that can be interpreted partially as analog circuits of a
kind pioneered by Bush in 1930, and extended and speculated later by Rubel working on ShannonÕs model
of BushÕs Differential Analyzer. This programming language make use of limits, a mathematical concept that
is not in general physically realizable. Thus (invoking informally the physical CT Thesis) such computational
model is beyond the Turing limit, although functions remain constructible and countable in number. The
hypercomputational character of the model has, however, nothing to do with the fact it handles real numbers
and real numbers (as in [30]) can code for non-computable functions. The hypercomputational capabilities
are associated with the operators, especially with the taking of limits.
How powerful it is, this model suffers from the same classical limitations as the standard Turing model of
computation: the classical results of computability theory can be parameterized to our programming language
to show that, e.g., the halting problem of analog computation is not solvable. This is quite different from [30],
since although real (but non-computable) numbers are incorporated in their model (as net weights), neural
nets with real weights are not countable and thus the same diagonalization methods of classical computability
can not be applied to a set of non-countable nets. Herein, we have the same s–m–n theorem and the same RiceÕs
theorem as in classical computability but with different interpretations.

8. Conclusions

Let us summarize the article with a few remarks concerning the relation between analog computation and
hypercomputation.
First, the use of real numbers does not lead automatically to a possibility of computations beyond Turing
borders. We could observe that although GPAC is an analog device it can only find solutions to such problems
which can be solved (approximately but with any desirable precision) by Turing machines [26] too.
Next, the study of analog computation does not have to be inspired by hypercomputational motivation.
There are good reasons to see analog computation as a useful tool of mathematics to study problems of clas-
sical computability (with already obtained results in such fields as GrzegorczykÕs hierarchy [3,2]), complexity
theory [19] and arithmetical hierarchy [18]. Moreover, there are some results which can compare analog com-
putation with fields of mathematics (e.g., descriptive set theory [14]). Hence, the results for various models of
analog computation should not be treated as the direct support for hypercomputation.
However, it could be admitted that on some levels of analog computations (in the g-hierarchy [18] or, prob-
ably, for EAC-computable functions [27]) we can find classically uncomputable functions. Let us point out
that some tools for descriptions of such functions are also given in classical computability theory. Namely,
the upper levels of the arithmetical hierarchy or degree theory consists of uncomputable, in Turing sense, func-
tions [21]. So, it would be suggested that such wide and rich theories of analog computation do not speak
about real possibility of computation, but form degrees of uncomputability by finding and classifying main
uncomputable operators and structures. We believe that the current results give the strong support for the the-
sis of an existence of natural connection between uncomputable character of some function and infinite limits
involved (explicitly or implicitly) in its definition.
Finally, we think that an important aspect of the discussions of hypercomputation is connected with phys-
ics. Hence, the question about possibility of some computation beyond Turing limit is the question about nec-
essary conditions for physical theories describing our Universe. In this aspect analog computation has some
importance, as the theory closer in its formulation to physical theories than classical computability theory.

References

[1] L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, 1998.
[2] O. Bournez, E. Hainry, An analog characterization of elementarily computable functions over the real numbers, in: Proceedings of
Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Lecture Notes in Computer Science, vol.
3144, Springer-Verlag, 2004, pp. 269–280.
 J. Mycka / Applied Mathematics and Computation 178 (2006) 103–117 117

[3] M.L. Campagnolo, C. Moore, J.F. Costa, An analog characterization of the Grzegorczyk hierarchy, J. Complexity 18 (4) (2002) 977–
1000.
[4] G.J. Chaitin, The Limits of Mathematics, Springer, 1998.
[5] B.J. Copeland, Even Turing machines can compute uncomputable functions, in: C.S. Calude, J. Casti, M.J. Dinneen (Eds.),
Unconventional Models of Computation, Springer-Verlag, 1998.
[6] N.J. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge University Press, 1980.
[7] N.C.A. da Costa, F.A. Doria, Undecidability and incompleteness in classical mechanics, Int. J. Theor. Phys. 30 (8) (1991) 1041–1073.
[8] G. Etesi, I. Nemeti, Non-Turing computations via Malament–Hogarth spacetimes, Int. J. Theor. Phys. 18 (2002) 341–370.
[9] A. Grzegorczyk, On the definition of computable real continuous functions, Fund. Math. 44 (1957) 61–71.
[10] P. Koiran, C. Moore, Closed-form analytic maps in one or two dimensions can simulate Turing machines, Theor. Comput. Sci. 210
(1999) 217–223.
[11] C. Moore, Complexity in dynamics systems, Ph.D. Dissertation, Cornell University, 1991.
[12] C. Moore, Generalized shifts: unpredictability and undecidability in dynamical systems, Nonlinearity 4 (1991) 199–230.
[13] C. Moore, Recursion theory on the reals and continuous-time computation, Theor. Comput. Sci. 162 (1996) 23–44.
[14] J. Mycka, Real recursive functions and Baire classes, Fund. Inform. 65 (3) (2005) 263–278.
[15] J. Mycka, l-Recursion and infinite limits, Theor. Comput. Sci. 302 (2003) 123–133.
[16] J. Mycka, J.F. Costa, The computational of continuous dynamic systems, in: Machines, Computations, and Universality: 4th
International Conference, MCU 2004, Saint Petersburg, Russia, Lecture Notes in Computer Science, vol. 3354, 2005, pp. 164–175.
[17] J. Mycka, J.F. Costa, Undecidability in continuous dynamic systems, Logic J. IGPL, in press.
[18] J. Mycka, J.F. Costa, Real recursive functions and their hierarchy, J. Complexity 20 (6) (2004) 835–857.
[19] J. Mycka, J.F. Costa, The P 5 NP conjecture in the context of real and complex analysis. J. Complexity, in press.
[20] W. Newton-Smith, The Structure of Time, Routledge & Kegan Books, 1984.
[21] P. Odifreddi, Classical Recursion Theory, Elsevier, 1989.
[22] R. Penrose, The EmperorÕs New Mind, Oxford University Press, 1989.
[23] M.B. Pour-El, Abstract computability and its relation to the general purpose analog computer, Trans. Am. Math. Soc. 199 (1974) 1–
28.
[24] Y. Rogozhin, Small universal Turing machines. Universal machines and computations, Theor. Comput. Sci. 168 (2) (1996) 215–240.
[25] L.A. Rubel, Some mathematical limitations of the General-Purpose Analog Computer, Adv. Appl. Math. 9 (1988) 22–34.
[26] L.A. Rubel, Digital simulation of analog computation and ChurchÕs thesis, J. Symb. Logic 54 (3) (1989) 1011–1017.
[27] L.A. Rubel, The extended analog computer, Adv. Appl. Math. 14 (1993) 39–50.
[28] O. Shagrir, I. Pitowsky, Physical hypercomputation and the Church–Turing thesis, Minds Mach. 13 (2003) 87–101.
[29] C. Shannon, Mathematical theory of the differential analyser, J. Math. Phys. MIT 20 (1941) 337–354.
[30] H.T. Siegelmann, E.D. Sontag, Analog computation via neural networks, Theor. Comput. Sci. 131 (1994) 331–360.
[31] I. Stewart, Deciding the undecidable, Nature 352 (1991) 664–665.
[32] F. Tipler, The physics of immortality: modern cosmology, God and the resurrection of the dead, Anchor (1997).
[33] Z. Xia, The existence of noncollision singularities in newtonian systems, Ann. Math. 135 (3) (1992) 411–468.
[34] X. Zheng, K. Weihrauch, The arithmetical hierarchy of real numbers, Math. Logic Quart. 47 (1) (2001) 51–65.