数理解析研究所講究録
1169 巻 2000 年 62-75

62Realistic models of computability on the real numbers
Vasco Brattka
Hagen, D-58084 Hagen, Germany
Theoretische Informatik I,-mail: vasco.brattka@fernuni-hagen.de$\mathrm{F}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{i}\mathrm{t}\dot{\mathrm{a}}\mathrm{t}$$\mathrm{e}$April 26, 2000
Abstract

In this paper we discuss the role of the model of computability in the cycleof real number programming. We argue that problems occurring in practice, likeinstability or degeneracy problems, are caused by the real number model. As amore realistic approach we propose the point of view of computable analysis and we
present a feasible real number model which is compatible to this approach. Finally,
we briefly discuss a general theory of continuous data structures which is based oncomputable analysis.
Keywords: real number model, computable analysis, continuous data structures.

1

Introduction

We will start to discuss the role of the model of real number computation in the cycleof real number programming. Typically, this cycle can be characterized by the following
three steps (cf. Figure 1):(1) Description: in a first step the problem under consideration is described in terms
which are offered by some given model of computation on the real numbers.
(2) Programming: in a second step the model of computation is used to develop somealgorithm which solves the problem. Thus, “programming” here means “developing
algorithms”(3) Implementation: last not least, the algorithm is implemented in some concrete
programming language on a physical computer.

It is easy to realize that this cycle of real number programming sensitively relies on
the chosen model of computability on the real numbers. This model already determines
the description of the problem, as well as the construction of the algorithm. Moreover, it
depends on the model of computability whether a correct implementation of the algorithm
on physical computers will be possible or not.
It is the real number model which is used as the standard model of computability on
the real numbers in various parts of computer science and mathematics. This model is63

Figure 1: The cycle of real number programming

based on the idea that real numbers are entities and formally it is introduced via registermachines or so-called real random access machines which are equipped with real number
registers and which can perform arithmetic operations as well as comparisons and equality
tests on real numbers precisely.
The real number model is the standard model in computational geometry (cf. Preparata
and Shamos [PS85] ; it has been used by Blum, Shub and Smale [BSS89] to introduce
a theory of computational complexity and by Traub, Wasilkowski and Woz’niakowsky[TWW88] to describe the complexity of algorithms in numerical analysis.
From a certain point of view the real number model is the mathematical formalizationof the semantics which is offered by typical imperative programming languages on thereal numbers. Languages like JAVA, , PASCAL and FORTRAN offer a data type “real”
together with arithmetic operations and comparisons. But unfortunately, this semantics
cannot be realized precisely on physical computers. This is not just a precision problemof floating point arithmetic but it is a general limitation of physical computers.
Heuristically, the problems of the real number model are well-known to practitioners,. numerical analysts know that comparisons with zero can be problematic and haveto be avoided. Special terminologies have been invented to describe the problems: theproblem under consideration can be called ill-conditioned, or a specific input can be calleddegenerated, or the algorithm can be called instable.
Rom the point of view of computable analysis the cardinal problem is that real numbers are infinite objects and in finite time we can only handle finite portions of information.
Consequently, discontinuous problems cannot be solved by physical machines. Especially,
the precise comparisons and equality tests of the real number model cannot be performedby physical computers.
The importance of the discontinuity problem depends on the specific area of application. For instance, in numerical analysis most of the algorithms treat continuous problems
like numerical integration; discontinuous problems like numerical differentiation have beenrealized as unsolvable in the general case. Even if an algorithm uses some discontinuous
test (like the Heron algorithm) this causes no problems in practice, since the corresponding problem is continuous (like the square root function). The situation in computational
geometry is quite different. There the problems under consideration are typically discon$)$$\mathrm{C}$$\mathrm{e}.\mathrm{g}$64tinuous (e.g. test whether a point belongs to some convex hull) and thus they cannot be
solved without the discontinuous basic operations of the real number model (cf. Hertlingand Weihrauch [HW94] and Burnikel, Mehlhorn, and Schirra [BMS94] . In the worst casethis can lead to algorithms which map typical inputs to completely incorrect outputs.
This phenomenon can also be illustrated by the function
$)$

$f$

$:\subseteq \mathbb{R}arrow \mathbb{R},$$(x, y)-\rangle\{$

1 if
if

$0$

$x\in \mathbb{Q}$$x\not\in \mathbb{Q},$$x^{2}\in \mathbb{Q}$)undefined in all other cases, which can be computed according to the real number model
but which can neither be approximately computed in a realistic sense nor be implemented).
correctly using floating point arithmetic (cf. Weihrauch
This highly unsatisfactory situation could be resolved by a Copernican turn: insteadof developing the best possible algorithms according to the real number model, one shouldsearch for the best possible model according to the abilities and limitations of physicalcomputers. As soon as such a model has been discovered, computer scientists should feel
free to replace the semantics of imperative programming languages by a semantics which
perfectly fits together with the new model.
Computable analysis is the right tool to figure out such a realistic model because
it is based on Turing machines. Following Church’s thesis, we can assume that Turingmachines describe the possibilities of handling finite information by physical machines in
the most realistic way according to our current knowledge.
We close the introduction with a short survey on the organization of the paper: inthe following Section 2 we will shortly discuss the model of computability which is usedin computable analysis. In Section 3 we present the feasible real random access machinemodel, which has been introduced in a joint project with Peter Hertling [BH98] andwhich is a realistic modification of the real number model with respect to computability
and complexity. Finally, in Section 4 we briefly discuss a general theory of continuous
data structures and we sketch how the ideas that have been applied to the real numbers
can be transferred to other objects like compact sets and continuous functions.
$[\mathrm{W}\mathrm{e}\mathrm{i}98|$2

Computable analysis

In this section we would like to present some basic definitions and results from computable
analysis which show how a realistic Turing machine based model of computability on thereal numbers can be defined. The origins of computable analysis go back to Turing’s
paper [Tur36] in which he presented his famous machine model. It is not very wellknown that one of his purposes was to introduce a formal definition for the notion of acomputable real number. The corresponding notion of a computable real number function
has systematically been studied by Grzegorczyk [Grz57] and Lacombe [Lac55] in thefiftieth. Later on, the theory of computable analysis has been developed by Hauck [Hau73],
Pour-El and Richards [PER89], Ko [Ko91] and Kreitz and Weihrauch [KW84] and manyothers. The presentation here will be mainly based on Weihrauch [WeiOO]. The basic idea

65

Figure 2: A Turing machine computing the square function$x-\rangle$$x^{2}$of computable analysis can be described in the following way: fix some representationof the real numbers by infinite sequences and call a real number function computable, if
there exists a Turing machine that transfers each sequence which represents some input
into a sequence which represents the corresponding output of the function. Figure 2
illustrates the situation for the square function with input in decimal representation.
More formally, we will first fix the notion of a representation.
$\pi$

Definition 2.1 (Representation) A representation of the real numbersfunction.

$\mathbb{R}$is a surjective$\delta:\subseteq\Sigma^{\omega}arrow \mathbb{R}$Heredenotes the set of infinite sequences over the alphabet the inclusion symbol
indicates a potentially partial functions. An example of a representation is theordinary decimal representation. Now it is straightforward to define the notion of acomputable real number function.
$\Sigma^{\omega}$$”\subseteq$$\Sigma$”

Definition 2.2 (Computable real number function) A functioniscalled computable with respect to some representation, if there exists some
Turing machine $M$ (with one-way output tape) which computes infinitely long and whichin the long run transforms each sequencewhich represents some $x:=\delta(p)\in \mathbb{R}$into some sequencewhich represents $f(x)$ , i.e.
.
$f:\subseteq \mathbb{R}arrow \mathbb{R}$$\delta:\subseteq\Sigma^{\omega}arrow \mathbb{R}$$p\in\Sigma^{\omega}$$q\in\Sigma^{\omega}$$f(x\grave{)}=\delta(q)$It is straightforward how to extend this definition to multi-dimensional functions. It is easy to observe that this definition of a computable real number
function sensitively relies on the chosen representation of the real numbers. Turing, whochose the ordinary decimal representation of the real number in his first attempt, realized
in a correction of his famous paper [Tur37] that the decimal representation has some serious disadvantages and other representations are preferable. Especially, he realized thefollowing:$f:\subseteq \mathbb{R}^{n}arrow \mathbb{R}$Proposition 2.3 (Decimal representation) Multiplication by 3, $i.e$ . the real function$x->3x$ is not computable with respect to the decimal representation.
:$f$$\mathbb{R}arrow \mathbb{R},$The proof by contradiction is quite easy: each machine which would compute multiplication by 3 w.r.t. the decimal representation has to transform the input $p=0.33333\ldots$

66

either to $q=$ 0.9999... or to $q’=$ 1.0000.... Especially, the machine has to write 0.9 or
1.0 on the output tape after some finite time, but no finite prefix of the input sequencesuffices to decide whether the correct output sequence has to start with 0.9 or with 1.0.
Consequently, such a machine cannot exist.
As a consequence of this phenomenon Turing did not abandon his machine model
for computations with real numbers but he replaced the decimal representation by someother representation. One possible choice of some reasonable representation is the so’which is defined like the decimal representation but
called “signed-digit
which also allows negative digits. From now on we will assume that is the binary signeddigit representation of the real numbers which operates with base 2 and digits $-1,0,1$ .
Computability of real number functions will be understood w.r.t. this representation.
Most concrete continuous functions which are used in analysis are computable in thissense.
$p$$\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}^{)}$$\delta$

Proposition 2.4 (Computable real functions) The real arithmetic $operations+,$ -,are computable real number$\exp$ :and the functions$\div:\subseteq \mathbb{R}^{2}arrow \mathbb{R}$$\mathbb{R}arrow \mathbb{R}$$\mathrm{s}\mathrm{i}\mathrm{n},$$\mathrm{c}\mathrm{o}\mathrm{s},$$.,$functions.

The proof for this and the following results in this section can be found in [WeiOO].
One of the main observations of computable analysis is that all computable real number
functions are continuous.
Theorem 2.5 (Continuity of computable functions) All computable real functions
are continuous.
$f$$:\subseteq \mathbb{R}^{n}arrow \mathbb{R}$Since each finite prefix of the output has to be computed from some finite prefix ofthe input, each finite prefix of the output has at least to depend on some finite prefix ofthe input. But this dependency is nothing but continuity. As a direct consequence one
obtains that the equality test on the real numbers is not decidable.
Proposition 2.6 (Undecidability of the equality) The equality test on the real numbers is not decidable, $i.e$ . the function
$e$

:

$0$
$\mathbb{R}^{2}arrow \mathbb{R},$$(x, y)\mapsto\{$if $x=y$

1 elseis not computable.

Now one could ask whether the undecidability of the equality is just a bad propertyof the signed-digit representation (in the same sense as the non-computability of themultiplication by 3 is just a bad property of the decimal representation). Unfortunately,
there is an easy cardinality argument which shows that equality is undecidable withrespect to all representations of the real numbers [WeiOO]. In other words: there is no
way to represent real numbers which could enable physical computers to decide equality!

67

Real number model
arbitrary constantsarithmetic operations are computable
precise tests $=,$$\exp$ are not computable

Computable analysis
only computable constantsarithmetic operation are computable
only finite precision tests$\exp$ are computable$<$$\mathrm{s}\mathrm{i}\mathrm{n},$$\mathrm{s}\mathrm{i}\mathrm{n},$$\mathrm{c}\mathrm{o}\mathrm{s},$$\mathrm{c}\mathrm{o}\mathrm{s},$Table 1: Models of computability on the real numbers

The following table summarizes some joint properties and some differences between thereal number model and the model of computability as it is used in computable analysis.
The property stated in the first line of the table is due to the fact that in the formalization of the real number model of Blum, Shub and Smale [BSS89] arbitrary constants
are allowed. This enables BSS machines to decide arbitrary discrete problems (the characteristic function can simply be stored in a constant). Thus, if one insists on arbitrary
constants then the model is not only unrealistic for topological reasons but also for recursion theoretic reasons. Moreover, the basic real number model is not only unrealistic but
also incomplete, since many important functions (like the trigonometric functions) are
not computable in this model because it does not offer any limit construction. Finally,
also the class of recursive sets which have been defined with the help of the real number
model is not very reasonable, since easy sets like the graph or the closed epigraph of the.
exponential functions are not recursive in this sense$[\mathrm{B}\mathrm{r}\mathrm{a}99\mathrm{a}]$Feasible real random access machines

3

In the previous section we have seen how a realistic Turing machine based model ofcomputability on the real numbers can be defined. One problem related to this model isthat it will be difficult to convince practitioners in computational geometry or numericalanalysis to describe their algorithms in terms of Turing machines. In this section wewould like to introduce the so-called feasible real random access machine model (feasibleRAM) which overcomes this problem since it characterizes the Turing machine approachof computable analysis in terms as close as possible to the real number model. The feasible
real random access machine model as well as all presented results are due to ajoint projectwith Peter Hertling [BH98]. The feasible real RAM can be characterized by the following
features:$\bullet$$\bullet$$\bullet$$\bullet$rational constants,

usual arithmetic operations on
ordinary tests $<,$$=\mathrm{o}\mathrm{n}\mathrm{N}$finite precision test$<_{k}$,

on$\mathbb{R}$,$\mathrm{N}$and$\mathbb{R}$,68$\bullet$$\bullet$approximative semantics,

logarithmic time complexity measure.

We will not formalize the definition of our feasible real RAMs but we will describe it
intuitively. Roughly speaking, a feasible real RAM is a register machine with two typesof registers: natural number registers and real number registers . A finite number ofthese registers can be used as input and output registers. The program of a feasible real
RAM is controlled by some finite flowchart. A precise list of all basic operations which
are allowed in flowcharts of the feasible real RAM together with there logarithmic costs
denotes roughly speaking theis given in the following table. The logarithmic cost
length of the binary representation of the integer part of . More precisely, fordenotes the binary logarithm:
we use $\ell(x)=1+\lfloor\log(\max\{|x|, 1\})\rfloor$ . Hereor$\log(x):=\log_{2}(x)$ .
$r_{j}$$n_{i}$$\ell(x)$$x\in \mathrm{N}$$x$$\log$$x\in \mathbb{R}$$r_{i}:=q$

cost $(op)$11$n_{i}:=n_{j}$$l(n_{j})$$op$assignment of constants$n_{i}:=m$simple copy instructions

mixed copy instructions
natural arithm. operations
real arithmetic operations
tests

explanation$m\in \mathrm{N}$$q\in \mathbb{Q}$$r_{i}:=r_{j}$$\ell(r_{j})$$r_{i}:=n_{j}$$\ell(n_{j})$$n_{i}:=\lfloor r_{j}\rfloor_{n_{k}}$$\ell(r_{j}, n_{k})$$n_{i}:=n_{j}\otimes n_{k}$$\ell(n_{j}, n_{k})$$\otimes\in$$r_{i}:=r_{j}\otimes r_{k}$$\ell(r_{j}, r_{k})$$\otimes\in\{+)-, *\}$

$r_{i}:=r_{j}/r_{k}$$\ell(r_{j}, \frac{1}{r_{k}})$$n_{i}=n_{j}$$P(n_{i}, n_{j})$$n_{i}<n_{j}$$\ell(n_{i)}n_{j})$$r_{i}<_{n_{k}}r_{j}$$\ell(r_{i}, r_{j}, n_{k})${$+$, $-,$$*,$$\mathrm{d}\mathrm{i}\mathrm{v}$, mod}

Table 2: Feasible RAM operations and their costs
The finite precision test$(X<_{ky})\ni\{$

TRUE
FALSE

$<_{k}$

with precision$k$can be defined precisely by$:\Leftrightarrow x<y$$: \Leftrightarrow x>y-\frac{1}{k+1}$$k\in$ N.
In other words: if the test $x<_{k}y$ answers with TRUE, thenforalways $x<y$ holds; and if the answer is FALSE, then $x>y- \frac{1}{k+1}$ holds. In the small
the answer of the test might be TRUE
overlapping area of uncertainty of length
as well as FALSE (cf. Figure 3). The reader should notice that the costs of the testof the overlapping area decreases. For complexity
operation increase if the length
reasons we will also use a finite precision staircase operation, giving one of the values in.
and$\lfloor x\rfloor_{k}:=\{n\in \mathrm{N}|n-\frac{1}{k+1}<x<n+1\}\cup\{0|x<0\}$ for$x,$ $’\iota’j\in \mathbb{R},$$\frac{1}{k+1}$$\frac{1}{k+1}$$x\in \mathbb{R}$$k\in \mathrm{N}$

69

$x$

Figure 3: The finite precision test

It is an important observation that the finite precision test introduces an indeterminism
into our feasible real RAM. More formally, a feasible real RAM computes a relation$R_{M}\subseteq X\cross Y$ where $(x, y)\in R_{M}$ if there is somecomputation path on input with
output . Here, $X,$ $Y$ denote finite products of and . But in contrast to the kind of
nondeterminism which is used in complexity theory, our indeterminism can be realizedon physical machines. Indeterminism and nondeterminism have in common that a single
input does potentially lead to several computation paths. While nondeterminism meansthat only some computation paths have to lead to a “valid result”, indeterminism meansthat all computation paths have to lead to a
result”. Thus, nondeterminism comeswith an existential quantification and indeterminism with an universal quantification in
the definition of semantics. To make this more precise we define our approximative
semantics.
$x$$\mathrm{N}$$y$$\mathbb{R}$$‘\langle \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}$Definition 3.1 (Approximative semantics) Let $M$ be a feasible real RAM with input
space
and output spaceand let $f:\subseteq Xarrow Y,$
be functions.
Then $M$ is said to approximate in time ifand$Y$$X\cross \mathrm{N}$$t:\subseteq X\mathrm{x}\mathrm{N}arrow \mathrm{N}$$f$(1) $d(f(x), y)<2^{-n}$ for all$t$$dom(f)\cross \mathrm{N}\subseteq \mathrm{d}\mathrm{o}\mathrm{m}(R_{M})$$(x, n)\in \mathrm{d}\mathrm{o}\mathrm{m}(f)\cross \mathrm{N}$(2) $t_{M}(x, n)\leq t(x, n)$ for all$(x, n)\in \mathrm{d}\mathrm{o}\mathrm{m}(f)\cross$and $y\in R_{M}(x, n)$ ,N.

Here denotes the maximum metric on , where is a finite product of the spaces
which are equipped with the discrete metric, Euclidean metric, respectively. Furthermore,denotes the logarithmic time complexity of the feasible real
$M$
RAM
which can be defined by
$Y$

$d$

$\mathrm{N},$$Y$$\mathbb{R}$$t_{M}:\subseteq X\mathrm{x}\mathrm{N}arrow \mathrm{N}$$t_{M}(x,$ $n)$$:=$$\max_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{s}\mathrm{o}\mathrm{n}}(x,n)\{\sum \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(op)\}$

comp.
$op$

for
where the last sum is over all operations $op$ in a computation pathon input $(x, n)$ and the maximum is over all computation paths on input $(x, n)$ . Thus, thelogarithmic time complexity measure charges each operation with costs depending on thesize of the operands. Now we are prepared to define time complexity classes for feasible
real RAMs. For
we define$(x, n)\in \mathrm{d}\mathrm{o}\mathrm{m}(R_{M})$$t:\subseteq X\cross \mathrm{N}arrow \mathrm{N}$$\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}_{\mathrm{R}\mathrm{A}\mathrm{M}}(t):=\{f$is a finite product of and and there isa RAM $M$ approximating in time.

$:\subseteq Xarrow Y|Y$$\mathbb{R}$$\mathrm{N}$$f$$\mathcal{O}(t)\}$

70

Our main result in this section will compare these time complexity classes with the corresponding time complexity classes for Turing machines. We recall the fact that in computable analysis the time complexity of a function measures the number of Turing ma(cf. Ko [Ko91],
chine steps which are used in order to produce the result with precision
if
M\"uller, Weihrauch [WeiOO] . Thus, a function $f:\subseteq Xarrow Y$ is in$M$binarytherespecttowithwhich computes
and only if there is a Turing machine
an approximation of $f(x)$ with precision
produceswhichandrepresentation
signed-digit
for each input sequence which represents in at most $t(x, n)$ steps. Precise definitions can be found in [BH98]. Now our main result can be stated as follows.
$2^{-n}$$\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}_{\mathrm{T}\mathrm{M}}(t)$$)$$[\mathrm{M}\ddot{\mathrm{u}}186]$$f$$2^{-n}$$x$$p$

Theorem 3.2 (Feasible real RAM) For regular time bounds
following inclusion holds:$t:\subseteq X\cross \mathrm{N}arrow \mathrm{N}$the.

$\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}_{\mathrm{T}\mathrm{M}}(t)\subseteq \mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}_{\mathrm{R}\mathrm{A}\mathrm{M}}(t)\subseteq \mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}_{\mathrm{T}\mathrm{M}}(t^{2}\cdot\log(t)\cdot\log\log(t))$

is called regular, if $P(x)+k+t(x, k+1)\subseteq \mathcal{O}(t(x, k))$Here a time boundand $t(x, k)\geq 2$ . This condition is fulfilled by all time bounds of practical interest. In
other words our result states that feasible real RAMs are a polynomially realistic modelof computability and complexity on the real numbers (compared to the Turing machine
based model of computable analysis). One of the surprising parts of the result is that is
suffices to use the logarithmic time complexity measure which only counts the sizes of theoperands but which does not measure the precision of the local RAM operations which isnecessary to compute the result.
$t:\subseteq X\cross \mathrm{N}arrow \mathrm{N}$Figure 4: The simulation of a RAM $M$ by a TM
The proof justifies this by the fact that the basic arithmetic operations are online. there are polynomial-time Rring machine programs
computable in polynomial time,
for these operations such that the output precision is equal to the input precision minusa certain fixed delay depending on the input size. This result can be extended to other$\mathrm{i}.\mathrm{e}$71larger classes of (smooth) basic operations like the exponential function or trigonometricfunctions (cf. [BH98]).
The main part of the proof which shows that feasible real RAMs can be simulated byTuring machines is based on the idea to start the simulation with a fixed input precision$m$ and to restart it again and again with a doubling of the input precision until the output
precision suffices. Because of regularity of the time bounds this doubling of precision will
not effect the time complexity substantially. The flowchart in Figure 4 illustrates the idea.

4

Theory of continuous data structures

In the previous section we have seen how an abstract description of the model of computability of computable analysis can be developed, which is realistic with respect tocomputability and complexity. From a certain point of view we can interpret this result such that we have found an efficient data structure for real and natural numbers.
This data structure can be summarized by the following table (where we have omitted
operations which are not necessary from the point of view of computability).

, discrete topology$\mathrm{N}$Naturals$\{0,1,2, \ldots\}$$0$

constant$0$$n$identity$\mathrm{i}\mathrm{d}:\mathrm{N}arrow \mathrm{N},$$n+1$successor function$\mathbb{R}$Realscomputable real numbers, Euclidean topology$0$constant$0$

1

constant

1$x+y$

addition$\mathbb{R}\cross \mathbb{R}arrow \mathbb{R},$$-X$

negation$\mathbb{R}arrow \mathbb{R},$multiplication$\mathbb{R}\cross \mathbb{R}arrow \mathbb{R},$inversion$\subseteq \mathbb{R}arrow \mathbb{R},$

limit

Lim

$x\cdot y$$1/x$$\lim_{narrow\infty}x_{n}$$s$:$\mathrm{N}arrow \mathrm{N},$$n-\rangle$$n$$n..\mapsto n+1$$(x, y)-,$ $x+y$$x-,$ $-x$$(x, y)-tx\cdot y$$x->1/x$$:\subseteq \mathbb{R}^{\mathbb{N}}arrow \mathbb{R},$$(x_{n})_{n\in \mathbb{N}}-* \lim_{narrow\infty}x_{n}$dom(Lim) $:=\{(x_{n})_{n\in \mathbb{N}} : (\forall n>k)|x_{n}-x_{k}|\leq 2^{-k}\}$$x<_{k}y$finite precision test$<_{k}$:$\mathbb{R}\cross \mathbb{R}\cross \mathrm{N}=\mathbb{N}$

Table 3: The structure of natural and real numbers

72

Of course, in the feasible real RAM the limit operation was not an explicit basic
operation but it was hidden in the approximative semantics.
In several areas of computer science we do not only want to compute with real numbers,
but we also want to compute with sets of real numbers and real number functions. In
numerical analysis we want for instance transform a program for a continuous function. Or in CAD we
into a program for its integral function:
want to compute with compact sets of real numbers and perform operations like the union
operation.
Consequently, the question appears how we can find suitable data structures not only
for the real numbers but also for other spaces like hyper and function spaces. We just wantto mention that an answer to this question can be given by the theory of perfect structures. These structures, taken as data structures for a suitable high-level programming language or computability model (like the feasible RAM model) allow to compute
exactly the same operations as the Turing machine model together with a corresponding representation. Moreover, perfect data structures have the following nice property$f$$x-\rangle$$[0,1]arrow \mathbb{R}$$\int_{0}^{x}f(t)dt$$[\mathrm{B}\mathrm{r}\mathrm{a}99\mathrm{b}]$$[\mathrm{B}\mathrm{r}\mathrm{a}99\mathrm{c}]$.

Theorem 4.1 (Stability Theorem) Perfect structures characterize their own computability theory.

Instead of defining the notion of a perfect structure formally, we just mention two
further examples.

$C[0,1]$

Continuousfunctionscomputable functions,
topology of uniform convergence

1

constant function$\{()\}arrow C[0,1],$ $()\mapsto\hat{1}$$\hat{1}$:$[0,1]arrow \mathbb{R},$ $x\mapsto 1$$f$identity$C[0,1]arrow C[0,1],$ $f-\rangle f$$y\cdot f$

scalar product$\mathbb{R}\cross C[0,1]arrow C[0,1],$$f+g$

addition$C[0,1]\cross C[0,1]arrow C[0,1],$$f\cdot g$

multiplication$C[0,1]\cross C[0,1]arrow C[0,1],$ $(f, g)rightarrow f\cdot g$$||f||$

norm$||||$

Limlimit$\mathrm{L}\mathrm{i}\mathrm{m}:\subseteq C[0,1]^{\mathbb{N}}arrow C[0,1],$:$C[0,1]arrow \mathbb{R},$$(y, f)-ry\cdot f$$(f, g)-tf+g$$f-,$ $\sup_{x\in[0,1]}|f(x)|$$(f_{n})_{n\in \mathbb{N}} \mapsto\lim_{narrow\infty}f_{n}$dom(Lim) $:=\{(f_{n})_{n\in \mathbb{N}} : (\forall n>k)||f_{n}-f_{k}||\leq 2^{-k}\}$Table 4: The structure of continuous functions
If we add to our data structure of the natural and real numbers the data structureoffor the space $C[0,1]$ of continuous functions from Table 4 and for the space$\mathcal{K}(\mathbb{R}^{n})$73non-empty compact subsets ofa perfect structure.

$\mathbb{R}^{n}$$\mathcal{K}(\mathbb{R}^{n})$Compact subsets$\{x\}$

injection$A$

identity$A\cup B$

union$d_{\mathcal{K}}$

Hausdorff metric

the data structure from Table 5, then we obtain again

recursive compact sets,
Vietoris topology$\mathbb{R}^{n}arrow \mathcal{K}(\mathbb{R}^{n}),$$x-\rangle\{x\}$$\mathcal{K}(\mathbb{R}^{n})arrow \mathcal{K}(\mathbb{R}^{n}),$$Arightarrow A$$\mathcal{K}(\mathbb{R}^{n})\cross \mathcal{K}(\mathbb{R}^{n})arrow \mathcal{K}(\mathbb{R}^{n}),$$d_{\mathcal{K}}$:$\mathcal{K}(\mathbb{R}^{n})\cross \mathcal{K}(\mathbb{R}^{n})arrow \mathbb{R}$$(A, B)-\rangle A\cup B$,$(A, B) \mapsto\max\{\sup_{a\in A}\inf_{b\in B}d(a, b),\sup_{b\in B^{a}}\inf_{\in A}d(a, b)\}$

Lim

limit

$\mathrm{L}\mathrm{i}\mathrm{m}:\subseteq \mathcal{K}(\mathbb{R}^{n})^{\mathrm{N}}arrow \mathcal{K}(\mathbb{R}^{n}),$$(A_{n})_{n\in \mathbb{N}}-, \lim_{narrow\infty}A_{n}$dom(Lim) $:=\{(A_{n}) : (\forall n>k)d_{\mathcal{K}}(A_{n}, A_{k})\leq 2^{-k}\}$Table 5: The structure of non-empty compact setsThus, we have here two possible datafor computations with objects likecompact sets and continuous functions. Of course, these structures represent only examples of data structures and there are other structures which correspond to different
topologies and computability notions on the same spaces. The tables mention the underlying topologies and the corresponding sets of computable points.
Moreover, the theory of perfect structures can answer the question which asks forreasonable data structures only with respect to computability and nothing is said aboutcomplexity. For complexity questions, a comprehensive and general theory of computational complexity of metric spaces is still missing.
$\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\dot{\mathrm{t}}\mathrm{u}\mathrm{r}\mathrm{e}\mathrm{s}$5Conclusion

In the introduction we have described the role of the computability model in the cycle ofreal number programming. As the cardinal problem of the real number model we havesingled out the discontinuity of the comparisons and equality tests. On the on hand, thiscauses a discontinuous description of the problem under consideration and, on the other
hand, this makes a precise implementation on physical computers impossible.
In Section 2 we have presented some basic results of computable analysis. Especially,it has been described precisely which computations on the real numbers can be performed
realistically on physical computers. One central result states that only continuous operations can be performed.

74

In Section 3 we have presented the feasible real RAM model which is an approach todescribe the results of computable analysis in terms which are as close as possible to thereal number model.
In Section 4 we have shown, at least on the level of computability, how these ideas canbe transferred to computations with other objects like compact subsets and continuousfunctions.
Finally, we propose to replace the original real number model in the cycle of real
number programming by the feasible real RAM model. Such a substitution would haveseveral advantages: on the one hand, real world problems, especially if they are inspired byphysical questions, are typically continuous. These problems can be described pretty goodby the continuous (but indeterministic!) feasible real RAM model. On the other handand maybe more important, each correct algorithm, developed for the feasible real RAM
model, can be implemented on physical computers without any instability or degeneracy
problems!

References[BH98]

Vasco Brattka and Peter Hertling. Feasible real random access machines. Journal of Complexity, $14(4):490-526$ , 1998.

[BMS94]

Christoph Burnikel, Kurt Mehlhorn, and Stefan Schirra. On degeneracy in geometric computations. In Proceedings of the Fifth Annual $ACM$-SIAM Symposium on Discrete Algorithms($Arlington_{f}$ VA, 1994), pages 16-23, New York, 1994. ACM.

[Bra99a]

Vasco Brattka. The emperor’s new recursiveness. preprint, 1999.

[Bra99b]

Vasco Brattka. Recursive and computable operations over topological structures. Informatik
Berichte 255, FernUniversit\"at Hagen, Fachbereich Informatik, Hagen, July 1999. Dissertation.

[Bra99c]

Vasco Brattka. A stability theorem for recursive analysis. In Cristian S. Calude and Michael J.
Dinneen, editors, Combinatorics, Computation Logic, Discrete Mathematics and Theoretical Computer Science, pages 144-158, Singapore, 1999. Springer. Proceedings of DMTCS’99
and CATS’99, Auckland, New Zealand, January 1999.
$\not\in y$[BSS89]Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over
the real numbers: $NP$ -completeness, recursive functions and universal machines. Bulletin of
the American Mathematical Society, 21 (1): 1-46, July 1989.

[Grz57]Andrzej Grzegorczyk. On the definitions of computable real continuous functions. Fundamenta
Mathematicae, 44:61-71, 1957.

[Hau73]

J\"urgen Hauck. Berechenbare reelle Funktionen.
Grundlagen der Mathematik, 19:121-140, 1973.

[HW94]

Peter Hertling and Klaus Weihrauch. Levels of degeneracy and exact lower complexity bounds
for geometric algorithms. In Proceedings of the Sixth Canadian Conference on Computational
Geometry, pages 237-242. University of Saskatchewan, 1994. Saskatoon, Saskatchewan, August 2-6, 1994.

[Ko91]

Ker-I Ko. Complexity Theory of Real Functions. Progress in Theoretical Computer Science.
Birkh\"auser, Boston, 1991.

Zeitschrifl f\"ur mathematische Logik und

75[KW84]

Christoph Kreitz and Klaus Weihrauch. A unified approach to constructive and recursive
analysis. In M.M. Richter, E. B\"orger, W. Oberschelp, B. Schinzel, and W. Thomas, editors,
Computation and Proof Theory, volume 1104 of Lecture Notes in Mathematics, pages 259-278,
Berlin, 1984. Springer. Proceedings of the Logic Colloquium, Aachen, July 18-23, 1983, PartII.

[Lac55]

Daniel Lacombe. Extension de la notion de fonction r\’ecursive aux fonctions d’une ou plusieurs
variables r\’eelles I. Comptes Rendus Acad\’emie des Sciences Paris, 240:2478-2480, June 1955.
The’orie des fonctions.

$[\mathrm{M}\ddot{\mathrm{u}}186]$

Norbert Th. M\"uller. Computational complexity of real functions and real numbers. Informatik
Berichte 59,
Hagen, Hagen, June 1986.
$\dot{\mathrm{F}}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{i}\mathrm{t}\ddot{\mathrm{a}}\mathrm{t}$[PER89]Marian B. Pour-El and J. Ian Richards. Computability in Analysis and Physics. Perspectives
in Mathematical Logic. Springer, Berlin, 1989.

[PS85]

Franco P. Preparata and Michael Ian Shamos. Computational Geometry. Texts and Monographs in Computer Science. Springer, New York, 1985.

[Tur36]

Alan M. Turing. On computable numbers, with an application to the “Entscheidungsproblem”.
Proceedings of the London Mathematic Society, 42 $(.2):230-265$ , 1936.
$al$[Tur37]

Alan M. Turing. On computable numbers, with an application to the “Entscheidungsproblem”.
A correction. Proceedings of the London Mathematical Society, $43(2):544-546$ , 1937.

[TWW88] Joseph F. Traub,. Wasilkowski, and H. Woz’niakowski. Information-Based Complexity.
Computer Science and Scientific Computing. Academic Press, New York, 1988.
$\mathrm{G}.\mathrm{W}$[Wei98]Klaus Weihrauch. A refined model of computation for continuous problems.
Complexity, 14:102-121, 1998.

[WeiOO]

Klaus Weihrauch.
appear).

Journal of

An Introduction to Computable Analysis. Springer, Berlin, 2000. (to