page 1  (31 pages)
2to next section

A domain-theoretic approach to computability

on the real line 1

Abbas Edalat and Philipp S?underhauf

Department of Computing, Imperial College
180 Queen's Gate, London SW7 2BZ
United Kingdom

fae,ps15g@doc.ic.ac.uk

Abstract

In recent years, there has been a considerable amount of work on using continuous domains in real analysis. Most notably are the development of the generalized Riemann integral with applications in fractal geometry, several extensions of the programming language PCF with a real number data type, and a framework and an implementation of a package for exact real number arithmetic.

Based on recursion theory we present here a precise and direct formulation of effective representation of real numbers by continuous domains, which is equivalent to the representation of real numbers by algebraic domains as in the work of Stoltenberg-Hansen and Tucker.

We use basic ingredients of an effective theory of continuous domains to spell out notions of computability for the reals and for functions on the real line. We prove directly that our approach is equivalent to the established Turing-machine based approach which dates back to Grzegorczyk and Lacombe, is used by Pour-El & Richards in their foundational work on computable analysis, and, moreover, is the standard notion of computability among physicists as in the work of Penrose. Our framework makes it possible to capture partial functions in an elegant way and it extends to the complex numbers and the n-dimensional Euclidean space.

1 Introduction

Computable analysis is traditionally approached from two different directions. On the one hand, we have the machine-oriented work, where computations are

1 Work supported by the EPSRC project Foundational Structures for Computer Science at Imperial College.

To appear in Theoretical Computer Science 21 October 1997

performed on a certain kind of abstract machine. Type 2 Theory of Effectivity (TTE) [20,40,41] falls into this class. In TTE, Turing machines operate on infinite tapes, the inscription of the tapes represent real numbers or other objects from analysis, for example subsets, functions or measures. The socalled Russian approach [5] is also of this type. The main difference with TTE lies in the restriction of input and output to computable elements. Although different in spirit, the recursive functions in the Blum-Shub-Smale model [4] can also be considered as machine-oriented. Real numbers are regarded as entities, but the computable functions are constructed from building blocks in a recursion-theoretic manner.

On the other hand, we have the analysis-oriented approach. Here concepts from classical analysis are effectively presented and used to develop a computability theory for real numbers. This approach to computable analysis originated from the work of Grzegorczyk [19] who classified Turing-machine computable real functions as those that map computable sequences to computable sequences and are effectively uniformly continuous. The work of Pour-El & Richards [29] is based on this definition and is now well-established and frequently cited in various communities including by physicists like Penrose [25].

The present paper is part of a programme to establish domain theory as a new approach to computable analysis. Domain theory was introduced independently by Dana Scott [32] for providing denotational semantics to functional programming languages and by Yuri Ershov [15] as a means to investigate partial computable functionals of finite type. The use of the so-called algebraic domains to model functional programming languages has become a well-established paradigm in computer science.

Various attempts have been made to use algebraic domains to represent classical spaces in mathematics. Weihrauch & Schreiber [43] constructed embeddings of Polish spaces (topologically complete separable metrizable spaces) into algebraic domains. Stoltenberg-Hansen and Tucker have shown how to represent complete local rings [35] and topological algebras, including locally compact Hausdorff spaces and the real line, by algebraic domains [36]. Di Gianantonio [6,7] has given an algebraic domain to model the real numbers. Blanck [3] has more recently shown how to embed complete metric spaces into algebraic domains.

In [36, Section 5.3], Stoltenberg-Hansen & Tucker use an algebraic domain to represent the real line and prove that the resulting notion of computable real function coincides with a slight strengthening of the approach by Pour-El & Richards. Also, the work in [36] allows them to generalise this result to Rn

and C which is explicitly done by Blanck in [3, Theorem 2.27].

However, a more general class, that of so-called continuous domains, is more

suitable to represent classical spaces. A continuous domain is a partially ordered set equipped with notions of completeness and approximation. The completeness axiom requires existence of least upper bounds for all directed subsets, approximation means that all elements arise as directed suprema of their essential parts or approximants. (All definitions are formally given in Section 2.) The particular case of continuous lattices [17] arises in many other branches of mathematics. The approximation axiom provides the link to the machine-based level of recursion theory or Turing machines: We will enumerate a convenient set of approximants and let the machine operate on this set.

The link to computable analysis on the real line is provided by the interval domain, the set of compact intervals of R, partially ordered with reversed set inclusion. Already in [32], Scott suggested the idea of using the interval domain to construct a real number data type. The real line embeds as set of maximal elements in this continuous domain. Thus the above mentioned approximation by partial elements corresponds to describing a real number as the intersection of a sequence of shrinking nested intervals which is a standard way of defining a real number in computable analysis [31]. Thus domain theory also provides a link to the well-established field of interval analysis [23] and can lead to new insights in this subject.

There has recently been a considerable amount of work in domain theory which could be classified as part of the programme Continuous domains in computable analysis". Most notably are the development of a domain theoretic framework for classical measure theory [11,9], the generalization of Riemann theory of integration [10] with applications in fractal geometry [12], several extensions of the programming language PCF with a real number data type [6,16,28], and a framework and an implementation of a package for exact real number computation [27,13]. This latter work is based on the one hand on continued fractions and linear fractional transformations as in [38,24] and on the other hand on the domain of intervals. These promising results suggest that a marriage of domain theory and computable analysis will indeed be fruitful for both subjects. The recent survey paper [8] gives an overview of these applications of continuous domains.

In this paper, we start a systematic exploration of the use of continuous domains for computable analysis. Here, we are concerned with analysis on the real line, the complex plane, and Rn. A forthcoming paper [14] will deal with metric spaces and Banach spaces. The main results in the present paper are the following: The domain-theoretic notions for computable real numbers and for computable functions coincide with the well-established so-called Polish approach which dates back to Grzegorczyk and Lacombe [18,21] and is equivalent to the above mentioned TTE-approach and to the definitions of Pour-El & Richards.

It can be shown using some general properties of algebraic and continuous domains that computability on the reals in our sense coincides with computability via the algebraic approach. Hence, apart from the slight strengthening of Pour-El & Richards' definition in [36], our results can be obtained from those in loc.cit. and vice versa.

Compared to the continuous domain approach, however, any representation of the real line by an algebraic domain is much more involved for topological reasons. The domain considered in [36] is the ideal completion of the set of all intervals with rational endpoints, and the real line is recovered as a quotient of the set of so-called total elements. In contrast, the continuous domain for the real line considered in the present paper is based on quite familiar and wellestablished notions in elementary analysis and the real line is simply embedded as its set of maximal elements.

In the present paper, we intend to promote domain theory as a means of investigating computability aspects in traditional mathematics. Therefore, we choose the more accessible continuous domain approach to computability and present the framework and the proofs directly in a self-contained way.

1.1 Plan of the paper

This paper is divided in two parts. Part I deals with the mathematical tools and Part II investigates the computability structure for the real line and briefly covers the n-dimensional Euclidean space and the complex plane.

To be self-contained, Part I starts in Section 2 with a short introduction to continuous domains in general and the interval domain in particular. The link to actual computations is provided by effective domain theory. Although it dates back to the origins of domain theory, we have included a section on this topic. The existing sources either consider algebraic domains only (e.g. [26,34]), or, as [33], concentrate on certain subclasses of continuous domains which are useful in denotational semantics but too special for our purpose. The only exception is the unpublished set of lecture notes in German by Weihrauch and Deil [42], where domains are considered as computational models very much in the same spirit as in the present paper. Unfortunately, this source is rather hard to access. There is a short published note [39] which contains the most basic definitions but lacks the results we need for our work. So we provide all the definitions and results needed and give proofs in Section 3 of this paper.

Part II is the core of our work. In Section 4, we define the notions of computable real numbers and sequences by effectively presenting the interval domain. These are shown to coincide with the corresponding standard notions

in classical computable analysis. Section 5 investigates the resulting notion of computable function on the real line. Again, the notion coincides with the standard one. As a corollary, we obtain a novel characterisation of computable functions: A function is computable if and only if it maps computable sequences of intervals to computable sequences of intervals. We conclude the paper by discussing real number representations within our framework.

1.2 Terminology

We will use the relevant notions from recursion theory as in the fairly standard language of [31]. The set f0; 1; 2; : : :g of natural numbers is denoted by N. The nth partial recursive function is denoted by OEn, the nth recursively enumerable (r.e.) set by Wn, so that Wn = dom(OEn). We will make use of a standard pairing function h?; ?i: N?N ! N which could be defined as hn; mi = 12 (n2+2nm+m2+ 3n+m). The projections are denoted by ss1; ss2; they satisfy hss1(n); ss2(n)i = n as well as ss1(hn; mi) = n and ss2(hn; mi) = m for all n; m 2 N. As usual, a relation R ? N?N is said to be r.e. if the set fhn; mi j (n; m) 2 Rg is r.e. We will conveniently say that R is r.e. in n; m. Similarly for relations of higher arity.

Many of our results have the form There is f with property A iff there is g with property B". Sometimes, we add the phrase This equivalence is effective." This means that there are partial recursive function 1; 2: N ! N such that if OEn has property A then 1(n) is defined and OE 1(n) has property B and, conversely, if OEm has property B then 2(m) is defined and OE 2(m) has property A. Similarly for r.e. sets in place of functions. This is referred to as uniformity by Rogers in loc.cit.

We will employ the dovetailing principle in the form of the following construction: Every r.e. set A ? N can be written as the union A = Sn2NAn of an increasing chain A0 ? A1 ? A2 ? ? ? such that the relation i 2 An is recursive in i; n. To see that this is true, we take a Turing machine based approach to recursion theory. If M is a machine which produces a list of the elements of A, then define An to contain those elements produced after n steps of computation by M . A consequence of effectiveness of this construction is the Selection Theorem [31, Theorem 5-XVIII]. It says that there is a partial recursive function : N ! N such that (n) is defined iff the set Wn is not empty in which case (n) 2 Wn.

Part I: Mathematical Tools

2 Continuous domains

Domain theory was introduced by Dana Scott in [32] as a mathematical theory of computation. See [1] for a detailed treatment of domain theory, in particular for topics which are not of interest here, but are important for denotational semantics, e.g. cartesian closed categories and solution of recursive domain equations. In this section, we give a short introduction to continuous domains as computational models, a topic which has become an active area of research in recent years.

2.1 Basic definitions

The first basic notion is that of a partially ordered set (poset) (D; v). This is a set D equipped with a binary relation v which is

reflexive: x v x for all x 2 D,
transitive: x v y and y v z implies x v z for all x; y; z 2 D,
antisymmetric: x v y and y v x implies x = y for all x; y 2 D.

The elements of D are thought of as descriptions of some objects. The order is referred to as order of information. Indeed, x v y is understood as y carries more information than x". From this it is apparent that the set of maximal elements, denoted by max(D), will be of special interest. A non-empty subset A ? D is directed, if for all x; y 2 A there is z 2 A with x v z and y v z. Important examples of directed sets are increasing chains. These are sets A = fa0; a1; a2; : : :g such that a0 v a1 v a2 v ? ? ? : We think of such a chain as a stepwise computation: in each step we gain more information about the computed entity. What would this entity be? An element containing precisely all the information gained during the computation, which is exactly the notion of supremum or least upper bound (lub): An element x 2 D is the lub of the subset A ? D if (1) it is an upper bound, i.e. a v x for all a 2 A and if (2) whenever b 2 D is any other upper bound then x v b. We write W" A = x to denote that the set A is directed and has lub x. The first axiom for domains is closure under these computations: A directed complete partial order (commonly abbreviated as dcpo) is a partially ordered set such that suprema for all directed subsets exist. We call the dcpo pointed, if it contains a least element ? (pronounced bottom").

If (D; v) is a dcpo and x; y 2 D then we say that x approximates y, and write x o y if for every directed subset A ? D with y v W" A there is

some a 2 A with x v a. If x0 v x, y v y0, and x o y then x0 o y0. The intuitive meaning of x o y is he information content of x is essential for y". It is frequently referred to as x is way-below y".

We now arrive at the definition of a continuous domain: We require that every element can be recovered from its essential ingredients.

Definition 1 A continuous domain is a dcpo (D; v) such that for every element x 2 D the set

##x = fy 2 D j y o xg

is directed and has x as its supremum:

_" ##x = x:

We often refer to a continuous domain simply as a domain. The single most important property of the order of approximation o on a continuous domain is the interpolation property: If x o y then there is z 2 D such that x o z and z o y. More generally: If xi o y for i = 1; : : : ; n then there is z 2 D with xi o z for i = 1; : : : ; n and z o y.

The unit interval [0; 1] in its usual order serves as an example of a continuous domain. Here x o y iff x = or x < y. Similarly, the extended non-negative
reals [0; 1] with the usual ordering form a continuous domain.

The Scott-topology of a dcpo (D; v) consists of all subsets O of D which are upwards closed (x 2 O; x v y =) y 2 O) and inaccessible by directed suprema, i.e. if W" A 2 O then O A <> ;. This topology is always T0 but typically not T1. If D is a continuous domain, then, as a consequence of the interpolation property, the sets ""x = fy 2 D j x o yg for x 2 D are Scott-open. Moreover, they form a basis for the topology. A function f : (D; v) ! (E; v) between dcpo's is continuous with respect to the Scott-topologies on D and E if and only if it is monotone and preserves suprema of directed subsets: x v y implies f(x) v f(y) and f(W" A) = W" f(A). A function f between pointed dcpo's is called strict if f(?) = ?. The collection of all Scott-continuous functions from D to E is denoted by [D ! E]. It is endowed with the pointwise order, i.e., f v g iff f(x) v g(x) for all x 2 D, which makes [D ! E] a dcpo.

The nontrivial Scott-open subsets in the above examples ([0; 1]; <=) and ([0; 1]; <=) are of the form (a; 1] and (a; 1], respectively. An endofunction on [0; 1] is Scott-continuous iff it is monotone and lower semicontinuous in the traditional sense. In general, a function f : X ! [0; 1] from any topological space X is continuous with respect to the Scott-topology on [0; 1] iff it is lower semicontinuous.

A subset B of a domain (D; v) is a basis if every element of D is the directed supremum of all basis elements approximating it:

x = _"(##x B):

Every domain D has a basis, namely D itself. A domain is !-continuous, if it has a countable basis. In each of the above examples the set of all rational numbers in the domain forms a basis; hence both [0; 1] and [0; 1] are !- continuous.

If D and D0 are domains then so is their direct product, D ? D0. The order and order of approximation are coordinatewise, i.e.

(x; x0) v (y; y0) () x v y & x0 v y0

and

(x; x0) o (y; y0) () x o y & x0 o y0:

The Scott-topology on the product coincides with the product topology of the Scott-topologies on the factors. Unlike the situation in general topology, it is true that a function f : D ? D0 ! E is Scott-continuous if and only if it is Scott-continuous in both variables separately. This is due to the fact that Scott-continuity can be characterised purely in order-theoretical terms.

2.2 The interval domain

The interval domain I gives the set R of real numbers a computational structure. It is the collection of all compact intervals, endowed with a least element:

I = f[a; b] ? R j a; b 2 R; a <= bg [ f?g

The order is reversed subset inclusion, i.e. ? v I for all I 2 I and [a; b] v [c; d] iff a <= c and b >= d in the usual ordering of real numbers. One can think of the least element ? as the set R. Directed suprema are filtered intersections of intervals. The way-below relation is given by I o J iff int(I) ? J , where int(I) denotes the interior of I. Thus ? o I for all I 2 I and [a; b] o [c; d] iff a < c and b > d. The maximal elements are the intervals [a; a], i.e. the singleton sets.

The interval domain can be thought of as a triangle as depicted in Figure 1. The upper edge of this triangle corresponds to the set of maximal elements,

?
?
?
?
?
?
?
?
?
?
?
?
?
??J
J
J
J
J
J
J
J
J
J
J
J
J
JJ ?
?
??J
J
JJr
fag r
fbg

r
[a; b]

r?
Fig. 1. The interval domain.

i.e. to the real line. Points in the interior correspond to closed intervals of non-zero length. As shown in the figure, the endpoints of such an interval can be determined by drawing parallel lines to the side edges of the triangle and intersecting these with the upper edge. The thick line segment in the picture denotes the set ffxg j a <= x <= bg of maximal elements above the element [a; b] 2 I, which is mapped by fxg 7! x to the interval [a; b].

What is the Scott-topology on I? A base is given by the sets ""[a; b] = fI 2 I j I ? (a; b)g. So a base set for the relative Scott-topology on the set of maximal elements is of the form ""[a; b] max(I) = ffxg j x 2 (a; b)g. Under the canonical map fxg 7! x: max(I) ! R this is mapped to the open interval (a; b). Hence the set of maximal elements with the relative Scott-topology is homeomorphic to the real line via fxg 7! x.

Every continuous function f : R ! R has a Scott-continuous extension to the interval domain. This means that there is a Scott-continuous function g 2 [I ! I] such that g(fxg) = ff(x)g holds for all x 2 R. Moreover, among those extensions which are strict in the sense that g(?) = ? there is a largest one. It is explicitly given by

g(I) = ff(x) j x 2 Ig

for I <> ?. Since the non-bottom elements of the interval domain are exactly the compact connected subsets of R and as the operation of taking the direct image under a continuous function preserves both these properties, it is immediate that the function g is well-defined.

A convenient computational model for a compact interval A ? R is defined in the same manner. We denote with IA the interval domain of A, consisting of all compact intervals contained in A:

IA := f[a; b] ? A j a <= bg:

The order is reversed subset inclusion as before. Note that A itself is a compact interval, so A 2 IA and we do not need to add a least element. The above results for I concerning the Scott-topology and extensions of continuous functions do also hold for IA. We can in addition consider continuous functions f : A ! B for A and B different compact intervals or the real line; those extend to the interval domains as before. If A is a compact interval rather than the real line R, then we can drop the assumption of strictness to find a largest extension.

3 An effective theory of continuous domains

The material covered in this section is rather well-known among domain theorists with interest in recursion theory. Unfortunately, there is no simply available source on the subject as mentioned in the introduction. We develop the theory along the lines of [42].

3.1 Effectively given domains

Definition 2 Suppose (D; v) is an !-continuous pointed domain with countable basis D0 = fb0; b1; b2; ? ? ?g. It is effectively given with respect to b if the relation bn o bm is r.e. in n; m. An element x 2 D is computable, if the set fn 2 N j bn o xg is r.e. Without loss of generality, we will henceforth assume that b0 = ?.

Remark. The reader might ask why we do not require the order of approximation o or the predicate bn = ? to be recursive (decidable). This is the approach in most other accounts of effective domain theory, e.g. [33] and the above mentioned Section 7 of [26]. These stronger assumptions (together with a restriction of the class of continuous domains) are needed in connection with the function space construction in order to yield a cartesian closed category of effective domains. As we are not interested in this topic here, we keep the definition as general as possible.

The computability structure on two effectively given domains induces an effective structure on their product as follows: If (D; v) and (D0; v) are effectively given with respect to (bn)n2N and (b0n)n2N, respectively, then the product D?D0

has the effective basis (b?n)n2N with b?hn;mi = (bn; b0m).

Proposition 3 An element x 2 D is computable iff it is the lub of an effective chain in D0, i.e. iff there is f : N ! N total recursive such that bf(0) v bf(1) v bf(2) v ? ? ? and x = W"n2Nbf(n). This equivalence is effective. Moreover, the chain can be chosen to be a o-chain, i.e. such that bf(0) o bf(1) o bf(2) o ? ? ?.

PROOF. Suppose ##x D0 = fbg(n) j n 2 Ng for some total recursive g: N ! N. The function f : N ! N is defined inductively. First we put f(0) = g(0). To define f(n + 1) consider the set

An := fm 2 N j bf(n) o bg(m) & bg(n) o bg(m)g:

This set is r.e. as g is recursive. Furthermore, it is non-empty by the interpolation property of continuous domains. So we can apply the Selection Theorem to get an element an 2 An. Then f(n + 1) := g(an). The resulting function f gives an effective o-chain. We claim that its lub is x. To verify the claim, observe that f(n) 2 g(N) for every n 2 N. Hence bf(n) o x and so W"n2Nbf(n) v x. On the other hand, we have bg(n) v bf(n+1) for every n 2 N. Thus x = W"n2Nbg(n) v W"n2Nbf(n). This proves the claim, so the (only if) part of the proposition holds.

For the (if) part, note that if x = W"n2Nbf(n) then

bm o x () 9n 2 N: bm o bf(n):

This enables us to effectively obtain an index for ##x D0 from f . 2

We now define an enumeration ? of the set Dc of all computable elements. This is done in the following manner:

(1) Start with a natural number n.
(2) This describes a partial recursive function OEn: N ! N.
(3) Effectively construct an index n0 of a total recursive function OEn0 such that range(OEn0) = range(OEn) [ f0g. (Recall that b0 = ?.)
(4) Effectively get an index n00 of the total function OEn00 which is recursively defined by putting OEn00 (0) = OEn0(0) and the following procedure. (a) Start with i = and k = 1.
(b) The set A = f` >= k j bOEn00 (i) o bOEn0(`)g ? N is r.e.
(c) Write A = Sm2NAm, where the test ` 2 Am is recursive in `; m and where A0 ? A1 ? A2 ? ? ? ?.
(d) Now, starting with m = 1, each of these sets is tested for the existence of ` <= m with ` 2 Am. Whenever no such element is found, we put OEn00 (i +m) = OEn00 (i) and check for the next value of m.

(e) If, at some stage, there is ` <= m with ` 2 Am then let OEn00 (i +m) = OEn0 (`), increment i by m, set k = ` + 1, and go to step (4b).
Note that OEn00 defines an effective chain in range(OEn0): for each m 2 N we have either bOEn00 (m) o bOEn00 (m+1) or OEn00 (m) = OEn00 (m+ 1). Moreover, if range(OEn0) happened to be a chain already, then for each i 2 N there is j 2 N such that bOEn0(i) o bOEn00 (j) so that W"i2NbOEn00(i) = W" range(OEn0). (5) Now define ?(n) := W"i2NbOEn00(i).

Remark. Although the chain given by OEn00 as constructed is not a o-chain, it is possible to effectively obtain an effective o-chain from this by Proposition 3.

Proposition 4 Every element from D0 is computable. Moreover, there is a total recursive function k: N ! N such that ? ffi k = ? ffi b, where ?: D0 ,! Dc is the inclusion map.

PROOF. Clearly, for each n 2 N the set fm 2 N j bm o bng is r.e. and an index for it is effectively obtainable from n. As the equivalence in Proposition 3 is effective, we can construct the function k from this. 2

Lemma 5 The relation bn o ?(m) is r.e. in n and m.

PROOF. This is an immediate consequence of the fact that bn o W"i2Nbf(i) iff there is i 2 N with bn o bf(i). 2

Proposition 6 Least upper bounds of effective chains of computable elements are computable with effectively obtainable index.

PROOF. The set of basis elements way-below the supremum is the union of the sets of elements way-below the individual elements. This can be obtained effectively. 2

Remark. It is evident that Proposition 6 holds for effective directed sets in place of chains, too. Enumerations of Dc satisfying Lemma 5 and Proposition 6 are called admissible in [42]. In loc.cit., it is shown that all admissible enumerations are isomorphic, i.e. if ?; ?0: N ! Dc are both admissible then there is a recursive bijection f : N ! N with ? ffi f = ?0.

3.2 Computable functions

Definition 7 Suppose that the domains (D; v) and (D0; v) are effectively given with respect to b and b0, respectively. A continuous function f : D ! D0

is computable, if the relation

b0m o f(bn)

is r.e. in n; m.

Proposition 8 If f : D ! D0 between effectively given domains is computable then the relation

b0m o f(?D(n))

is r.e. in n; m.

PROOF. Note that

f(?D(n)) = f
?_" fy j y o ?D(n)g
?

=_" ff(y) j y o ?D(n)g

=_" fx0 2 D j 9y o ?D(n): x0 o f(y)g

=_" fb0m j 9i 2 N: bi o ?D(n) & b0m o f(bi)g

by continuity of f . Hence

b0m o f(?D(n)) () 9i 2 N: (b0m o f(bi) & bi o ?D(n)):

This is r.e. in n and m by Lemma 5 and the fact that f is computable. 2

Theorem 9 A continuous function f : D ! D0 between effectively given domains is computable iff there is a total recursive function : N ! N such that f ffi ?D = ?D0 ffi .

N - N

D

?D

? f - D0?

?D0

PROOF. (only if) Suppose that ?D(n0) = x. By Proposition 8, the relation b0m o f(?D(n)) is r.e. in n; m. So an index for

fm 2 N j b0m o f(?D(n0))g

is effectively obtainable from n0. This gives the function .

(if) Suppose f ffi ?D = ?D0 ffi . With k from Proposition 4 we have

b0m o f(bn) () b0m o f(?D(k(n)))

() b0m o ?D0( (k(n))):

This set is r.e. by Lemma 5 and recursiveness of ffi k. 2

Remark. Theorem 9 is part of the Myhill-Shepherdson-Theorem in this setting. What is missing is the fact that, roughly speaking, computability implies continuity. This means that if a recursive function : N ! N defines a function f : Dc ! D0c on the computable elements via ?D0 ffi = f ffi ?D, then this function f is necessarily Scott-continuous in the sense that it preserves all existing suprema of directed subsets. As we do not need this result here, we refer the reader to Satz 7 in [42] for the proof. Alternatively, the proof of Theorem 3.6.16 of [40]) which contains the result for the algebraic case can be translated to the continuous setting.

Using the concept of computable sequences, Theorem 9 can be put in a very appealing form.

Definition 10 A sequence (xn)n2N in D is computable, if there is a recursive function h: N ! N such that xn = ?D(h(n)).

Corollary 11 A continuous function f : D ! D0 between effectively given domains is computable iff it maps computable sequences to computable sequences.

PROOF. (if) As the identity on N is recursive, the sequence (?D(n))n2N is computable. Computability of the image sequence (f(?D(n)))n2N ensures computability of f by Theorem 9.

(only if) Assume that f is computable and pick : N ! N with f ffi ?D = ?D0 ffi (Theorem 9). If (xn)n2N is a computable sequence then there is h: N ! N recursive such that xn = ?D(h(n)). Then f(xn) = f(?D(h(n))) = ?D0( (h(n))) so the sequence (f(xn))n2N is computable since the function ffi h is recursive. 2

Remark. It is possible to have a unified framework for effectively presenting domains as suggested to us by Dana Scott. If one restricts to !-continuous bounded-complete domains, i.e. domains where every subset which is bounded above has a supremum, then there is a universal domain U . It has the property that every such domain is isomorphic to the image of a retraction on U . Thus an effective structure on U , which can be concretely constructed as the set of all non-empty closed subsets of the Cantor space under reverse inclusion, gives rise to effective structures on all domains which are computable retracts of U . Computable functions between such domains can be treated in a similar fashion. However, we do not take this approach here, firstly because it requires significantly more domain theory and secondly because, in the sequel [14] to this paper, we will apply the framework to Banach spaces and employ domains which are not bounded-complete.

Part II: Computability via Domain Theory

4 Computability on the real line

4.1 The effective interval domain

The interval domain I is !-continuous. An example for a countable basis is the collection I0 of all intervals with rational endpoints together with the least element ?. We will use this domain to endow the real numbers with a computable structure.

In order to proceed we first have to say how to deal with the set Q of rational numbers. We denote by q0; q1; q2; : : : a standard numeration of the rationals, e.g. qhn;hm;kii = n?m
k+1 . The arithmetic operations +; ?; ?; = as well as the comparisons
<; <=; = and the absolute value function j ? j on rationals are recursive in their indices.

Now we are ready to define an effective structure for the interval domain. We set

I0 = ?

and

Ihn;mi+1 = [qn ? jqmj; qn + jqmj]:

Clearly, this enumerates the basis I0. Let us check that the way-below relation is r.e. We have In o Im iff Im ? int(In) iff

n = or
?
m;n > and jqss1(n?1) ? qss1(m?1)j + jqss2(m?1)j < jqss2(n?1)j
?
;

so this relation is even recursive. It should be remarked that the particular choice of the basis and the enumeration for the basis is not essential for the theory as long as one can pass effectively back and forth between the bases. We picked the given enumeration as it makes the characterization of o particularly easy. The resulting enumeration of the computable elements of I is denoted by ?I : N ! I.

4.2 Computable numbers and sequences

A real number x 2 R is called left computable, if the set fn 2 N j qn < xg is r.e. Right computability is defined in an analogous way.

Proposition 12 An interval [x; y] 2 I is computable iff x is left-computable and y is right-computable.

PROOF. The interval is computable iff fn j In o [x; y]g is r.e. Now qn < x iff there are m; k 2 N such that qn = qm ? jqkj and Ihm;ki+1 o [x; y]. The relation qn > y can be characterised similarly, hence the proposition follows. 2

One possible definition of computability for a real number x is x is both leftand right-computable." From this it is an immediate consequence that a real number x is computable iff the set fxg is a computable element of the interval domain. We will obtain an effective version of this result in Corollary 19 below, using the approach via fast converging Cauchy-sequences of rationals to formulate computability for real numbers.

Definition 13 A real number x is computable, if there is a total recursive function h: N ! N such that

jqh(n) ? xj <= 1

2n

for all n 2 N.

Computable real numbers were first investigated by Turing [37]. Our definition is used by many authors (for early sources see e.g. [30,18]), is widely

accepted, and has many different equivalent characterizations. It is also used for constructive analysis in [2]. Before we proceed to the above mentioned result, we first turn our attention to the width of intervals. For I = [a; b] we set jIj = b ? a, for I = ? = R we define jIj = 1.

Lemma 14 1) The relation jInj <= qm is recursive in n; m.
2) The relation j?I(n)j < qm is r.e. in n; m.

PROOF. 1) We have jInj = 1 for n = and jInj = 2jqss2(n?1)j otherwise.
So (1) clearly holds.
2) As ?I(n) = TfIk j Ik o ?I(n)g it is true that j?I(n)j < qm holds iff there is k 2 N with Ik o ?I(n) and jIkj < qm. These two relations are r.e. by Lemma 5 and part (1), respectively. 2

It is well-known that it is not possible to effectively enumerate all computable real numbers (see, e.g. [40, Lemma 3.8.9]). The set of computable intervals, i.e. computable elements of the interval domain, however, can be enumerated with ?I . This gives rise to a partial enumeration of the set of computable real numbers.

Theorem 15 There is a partial recursive function h: N ! N such that h(n) is defined whenever ?I(n) is maximal in I and such that in this case OEh(n) is a total function which defines a fast converging sequence of rationals with limit xn, where ?I(n) = fxng.

PROOF. The relation R with

hn; k; ii 2 R () Ii o ?I(n) & jIij <= 1

2k (1)

is r.e. in n; k; i by Lemmata 5 and 14(1). Moreover, it is true that if ?I(n) is maximal and k 2 N there is i 2 N with hn; k; ii 2 R. By the Selection Theorem, there exists a partial recursive function g: N?N ! N such that

hn; k; g(n; k)i 2 R (2)

holds for all k whenever ?I(n) is maximal. Define j: N2 ! N by j(n; k) = ss1(g(n; k) ? 1). Then qj(n;k) is the middle point of the interval Ig(n;k). Now (qj(n;k))k2N is a fast converging sequence with limit xn: By (2) and (1) we have in particular xn 2 Ig(n;k). Now qj(n;k) 2 Ig(n;k) and jIg(n;k)j <= 2?k , so jxn ? qj(n;k)j <= 2?k as required. Finally, we define the function h to assign to a number n 2 N the derived index for the function sending k to j(n; k). 2

The converse of this is also true: If a sequence of rationals effectively converges, then an index for the limit is effectively obtainable from an index for the sequence. As we are going to prove this result for sequences of reals, we need some preparatory definitions.

Definition 16 A sequence (xn)n2N of real numbers is computable, if the sequence (fxng)n2N is computable in I. (In other words, if there exists a a total recursive function f : N ! N such that fxng = ?I(f(n)).)

We say that the sequence converges effectively to x 2 R, if there is g: N ! N recursive (the modulus of convergence) such that k >= g(n) implies jxk ? xj <= 2?n.

Lemma 17 The function (q; [a; b]) 7! [a?jqj; b+jqj]: Q?I ! I is computable.

Now we are able to prove the second half of the characterization of computable real numbers as promised above: limits of effectively convergent sequences are computable.

Theorem 18 If (xn)n2N is an effectively convergent computable sequence, then its limit x is computable. Moreover, an index for fxg can be obtained effectively from the indices for the sequence and the modulus of convergence.

PROOF. Assume g: N ! N is such that k >= g(n) implies jxk ? xj <= 2?n. Using Lemma 17 and effectiveness of the sequence (xn)n2N, we see that there is h: N ! N recursive such that

?I(h(n)) = [xg(n) ? 1

2n?1 ; xg(n) + 1

2n?1 ]: (3)

Then x 2 int(?I(h(n))) and fxg = Tn2N?I(h(n)). The interval sequence (?I(h(n)))n2N need not be shrinking, but the sequence (?I(h(2n)))n2N is. To see this, suppose y 2 ?I(h(2n + 2)). Then jy ? xg(2n+2)j <= 2?(2n+1). But jxg(2n+2) ? xj <= 2?(2n+2) and jx ? xg(2n)j <= 2?2n. So jy ? xg(2n)j <= 2?(2n+1) + 2?(2n+2) + 2?2n < 2?(2n?1). Thus y 2 int(?I(h(2n))).

Hence, via Proposition 6, an index for the function sending n to h(2n) is an index for fxg. 2

In particular, this result allows us to conclude that our notion of computable number coincides with the classical one.

Corollary 19 A real number x is computable if and only if the set fxg is a computable element of the interval domain.

PROOF. Theorem 15 yields one direction and Theorem 18 together with the fact that every computable sequence of rational numbers is a computable sequence of real numbers the other. 2

The effectivity of Theorems 15 and 18 enables us to show that our notion of computable sequence coincides with the notion introduced in [29].

Theorem 20 A sequence (xn)n2N is computable if and only if there is a recursive function r: N?N ! N such that jqr(n;k) ? xnj <= 2?k for all n; k 2 N.

PROOF. Assume that (xn)n2N is a sequence of reals and that r: N?N ! N is recursive such that jqr(n;k) ? xnj <= 2?k for all n; k 2 N. This means that (qr(n;k))k2N is a computable sequence effectively convergent to xn with the identity function as modulus of convergence. So we can apply Theorem 18 to effectively get an index for xn from r and n. This means that the sequence xn is computable.

Now assume that there is f : N ! N with ?I(f(n)) = fxng. By Theorem 15 there is a recursive function h: N?N ! N such that the sequence (qh(f(n);k))k2N is fast converging with limit xn. Thus we have a double sequence as required. 2

It is another immediate consequence of effectivity of Theorem 18 that Theorem 20 generalizes to double sequences of real numbers. A double sequence (xn;k)n;k2N of real numbers is said to be computable, if there is h: N ?N ! N recursive such that fxn;kg = ?I(h(n; k)) for all n; k 2 N.

Corollary 21 (Proposition 0-1 of [29]) Suppose (yn)n2N is a sequence of real numbers. If there is a computable double sequence (xn;k)n;k2N such that jxn;k ? ynj <= 2?k for all n; k 2 N, then the sequence (yn)n2N is computable.

4.3 Computability on Rn and C

It is clear that the nth power In of the interval domain may serve as computational model for the Euclidean space Rn. The elements of In are n-tuples of intervals. The function

(A1; : : : ; An) 7! A1 ? ? ? ? ?An

gives an isomorphism between In and the set

fA1 ? ? ? ? ?An j Ai 2 Ig

containing all n-dimensional rectangles whose edges are either compact intervals or the entire real line R. In this setting, again, the order v is reversed subset inclusion and o is reversed inclusion-in-the-interior. The set of rectangles with rational corner points serves as a basis for the domain. The enumeration J0; J1; J2; : : : of this basis is defined via the n-tupling function

(i1; ? ? ? ; in) 7! hi1; : : : ; ini: Nn ! N

with corresponding projections ssni : N ! N. We set

Jhi1;:::;ini = Ii1 ? ? ? ? ? Iin:

All the results from Section 4.2 readily generalize to the n-dimensional case. Occurrences of the absolute value jxj have to be replaced (where appropriate) by, for example, the 1-norm

k(x1; : : : ; xn)k = max(x1; : : : ; xn)

which is equivalent to the Euclidean norm. Width of intervals has to be replaced by the maximum width of the sides of the rectangles.

Having dealt with Rn we of course get immediately a computability theory for the complex plane C , via the identification C = R2.

5 Computable real functions

The domain theoretic notion of computable function gives rise to a natural definition of computable function on the reals.

Definition 22 A function f : R ! R is computable iff there is an extension g: I ! I (i.e. g(fxg) = ff(x)g for all x 2 R) which is computable in the sense of Section 3.

Employing Corollary 11 and the fact that the restriction of the Scott-topology on I to the set of maximal elements coincides with the usual topology of R, we immediately get:

Proposition 23 Every computable function R! R is continuous. A continuous function is computable if and only if it maps computable sequences of intervals to computable sequences of intervals.

We will show that this notion of computable function coincides with the classical notion of Grzegorczyk and Lacombe [18,21].

5.1 Equivalence with the classical notion

For the classical definition of computable real function, we use the re-formulation of [19] which Pour-El and Richards employ as a starting point for a detailed treatment of computable analysis [29].

Definition 24 A function f : R ! R is PR-computable iff (1) it maps computable sequences to computable sequences and (2) it is effectively uniformly continuous on intervals [?n; n], i.e. there is a recursive function h: N2 ! N such that jx ? yj <= 1
2h(n;k) & x; y 2 [?n; n] implies jf(x) ? f(y)j <= 12k for all
n; k 2 N and x; y 2 R.

Proposition 25 Suppose A ? R is a compact interval and f : A ! R is continuous. Then every Scott-continuous extension g: IA ! I of f satisfies the following property: For every " > there is ffi > such that jBj < ffi implies
jg(B)j < " for all compact intervals B ? A. Moreover, jx ? yj < ffi implies jf(x) ? f(y)j < " with " and ffi as above.

PROOF. Suppose " > 0. For each x 2 A, the function g is continuous at fxg. This means that there is ffix > such that B ? (x ? ffix; x + ffix) implies
g(B) ? (f(x) ? "2 ; f(x) + "2 ) for all B 2 IA. Now the interval A is entirely contained in the infinite union Sx2A(x? ffix2 ; x+ ffix2 ). So, by compactness, there is a finite set fx1; x2; : : : ; xng such that

A ? (x1 ? ffix1
2 ; x1 + ffix1
2 ) [ (x2 ? ffix2
2 ; x2 + ffix2
2 ) [ ? ? ? [ (xn ? ffixn
2 ; xn + ffixn
2 ):

Let ffi := min( ffix12 ; ffix22 ; : : : ; ffixn2 ). Suppose jBj < ffi. Then there is i 2 f1; 2; : : : ; ng with B ? (xi ? ffixi ; xi + ffixi ). Hence g(B) ? (f(xi)? "2 ; f(xi)+ "2 ). In particular jg(B)j < ", so the first part of the proposition is proved. For the second part, it suffices to remark that f ([a; b]) ? g([a; b]) holds for all a; b 2 A. 2

Theorem 26 Every computable function is PR-computable.

PROOF. Suppose f : R! R is computable with witnessing continuous computable extension g: I ! I. By Proposition 23 and Theorem 20, the function f maps computable sequences to computable sequences. We will obtain an effective modulus of continuity for f by using Proposition 25. Suppose n 2 N. Effectively construct a recursive function jn: N ! N such that

qss1(jn(2k+`)?1) = ?n + 2n ? `

2k and qss2(jn(2k+`)?1) = 2n

2k ;

i.e. such that

Ijn(2k+`) =
h
?n + 2n ? ` ? 1
2k ; ?n+ 2n ? ` + 1
2k

i

for all k 2 N and ` = 1; : : : ; 2k ? 1. Then define the relation R to consist of all triples hn; k; ii such that

8` 2 f1; : : : ; 2i ? 1g9`0 2 N: I`0 o g(Ijn(2i+`)) & jI`0j < 1

2k : (4)

This relation is r.e. as the set over which ` ranges is finite. We now claim that

hn; k; ii 2 R

=)
?
8x; y 2 [?n; n]: jx ? yj <= 2n

2i =) jg([x; y])j < 1

2k

?
(5)

=) hn; k; i + 1i 2 R: (6)

To see the first implication, assume hn; k; ii 2 R and x; y 2 [?n; n] with jx ? yj <= 2n2i . The intervals Ijn(2i+`) for ` = 1; ? ? ? ; 2i cover [?n; n] and have an overlap of width n
2i?1 . Thus there is ` with x; y 2 Ijn(2i+`). By definition
of R, there is `0 such that I`0 o g(Ijn(2i+`)) and jI`0j < 12k . In particular, this implies jg([x; y])j < 12k as required. For the second implication, assume that the formula in (5) holds. The interval Ijn(2i+1+`) has width 2n2i hence its image under g has width smaller than 12k . This implies that there is `0 2 N with jI`0j < 12k and such that g(Ijn(2i+1+`)) is contained in the interior of I`0. Hence hn; k; i + 1i 2 R.

By the implication in (6), continuity of f on intervals [?n; n], and Proposition 25, for all n; k 2 N there is i 2 N such that hn; k; ii 2 R. Hence, by the Selection Theorem, there is h: N2 ! N total recursive such that hn; k; h(n; k)i 2 R for all n; k 2 N. This function is an effective modulus of continuity for f by the implication in (5) and Proposition 25. 2

We now consider maxima of PR-computable functions. Pour-El and Richards show that the sequence of maxima of a computable sequence of functions on a fixed interval is a computable sequence of real numbers [29, Theorem 0.7]. Their proof can be adopted to a similar situation: the sequence of maxima of a fixed function on a sequence of intervals.

Proposition 27 If f : R ! R is PR-computable and h: N ! N n f0g is recursive, then the sequence (max(f(Ih(n))))n2N is a computable sequence of real numbers.

PROOF. As h(n) > we have Ih(n) <> R for all n 2 N; so the sequence is
well-defined. We assume that g: N2 ! N is the recursive modulus of continuity for f , i.e. that

jx ? yj <= 1

2g(n;k) & x; y 2 [?n; n] =) jf(x) ? f(y)j <= 1

2k (7)

for all n; k 2 N. There is j: N ! N total recursive such that

Ih(n) ? [?j(n); j(n)] (8)

for all n 2 N. Define ff: N2 ! N total recursive such that

ff(n; k) >= 2g(j(n);k) ? 2jqss2(h(n)?1)j;

then

jIh(n)j

ff(n; k) <= 1

2g(j(n);k) : (9)

Now set

sn;k = maxff(qss1(h(n)?1)) + i

ff(n; k) jIh(n)j
| {z }
:=xn;k;i

) j 1 <= i <= ff(n; k)g:

Then (sn;k)n;k2N is a computable double sequence of real numbers. Suppose f attends its maximum on Ih(n) at ^x 2 Ih(n). There is i 2 f1; : : : ; ff(n; k)g such

that j^x ? xn;k;ij <= jIh(n)j
ff(n;k) . Hence

j^x ? xn;k;ij <= 1

2g(j(n);k) (10)

by (9). Combining (7) with (8) and (10) yields jf(^x) ? f(xn;k;i)j <= 12k . But f(xn;k;i) <= sn;k <= f(^x) by definition of sn;k and ^x. Thus j max(f(Ih(n))) ? sn;kj <= 12k and the sequence is computable by Corollary 21. 2

Lemma 28 If (xn)n2N is a computable sequence of real numbers then the predicate

xn < qm

is r.e. in n and m.

PROOF. There is a recursive function c: N2 ! N such that

jqc(n;i) ? xnj <= 1

2i for all i 2 N: (11)

Now xn < qm holds iff there is i 2 N with

xn + 1
2i < qm: (12)

Using (11), we see that (12) implies qc(n;i+1) + 12 i+1 < qm. On the other hand, qc(n;i) + 12i < qm certainly implies xn < qm. So we have

xn < qm () 9i 2 N: qc(n;i) + 1

2i < qm

and the latter predicate is r.e. 2

Theorem 29 Every PR-computable function is computable.

PROOF. Suppose f : R ! R is PR-computable. Denote by ?f : I ! I the largest strict extension of f to the interval domain, i.e. ?f (?) = ? and ?f (J) = f(J) is the forward image of J under f for all J 2 I. Now

Im o ?f (In) () m = or (n > & [minf(In); maxf(In)] ? int(Im))

() m = or
?
n; m > &

minf(In) > qss1(m?1) ? jqss2(m?1)j &

maxf(In) < qss1(m?1) + jqss2(m?1)j
?
:

This relation is r.e. by Proposition 27 and Lemma 28. Hence f is computable. 2

Theorems 26 and 29 show that our approach is equivalent to the one by PourEl & Richards and therefore to that of TTE and Grzegorczyk's definition:

Corollary 30 A function is computable if and only if it is PR-computable.

In conjunction with Proposition 23, this yields a novel characterisation of PR- computability which sheds new light on the difference with the computability notion of Banach-Mazur [22], also known as sequential computability (A function is computable in this sense iff it preserves computability of sequences of real numbers.)

Corollary 31 A continuous function is PR-computable if and only if it maps computable sequences of intervals to computable sequences of intervals.

Corollary 32 If a function f : I ! I is computable, strict, and maps maximal elements to maximal elements then the largest strict continuous function above f is computable.

5.2 Partial functions

For f : I ! I we let

Df = fx 2 R j f(fxg) 2 max(I)g

be the domain of the associated partial function on the real line. Our aim is to characterize the partial computable functions of reals in the spirit of [29]. As a starting point, we derive from Corollary 11

Proposition 33 If f : I ! I is computable and (xn)n2N is a computable sequence of reals in Df then the sequence (f(xn))n2N is computable.

Proposition 34 Suppose f : I ! I is computable. Then there is a recursive function such that (n), for n >= 1, is the index for a modulus of continuity on In if and only if In ? Df .

PROOF. This is essentially the same as the second part of the proof of Theorem 26. It is a little harder as the boundaries are more complicated. With the abbreviations an = qss1(n)?1 ? jqss2(n)?1j (i.e. In = [an; an + 2jqss2(n)?1j]), we define jn: N ! N for n > in such a way that

qss1(jn(2k+`)?1) = an + ` jInj

2k and qss2(jn(2k+`)?1) = jInj

2k ;

i.e. such that

Ijn(2k+`) =
h
an + (` ? 1) jInj

2k ; an + (` + 1) jInj

2k

i

for all k 2 N and ` = 1; : : : ; 2k ? 1. The resulting function h(n; k) will be total for fixed n if and only if In ? Df . 2

Almost the same is possible for computable intervals. We only have to take care to exclude all indices for the least element of I.

Proposition 35 Suppose f : I ! I is computable, Then there is a recursive function such that whenever ?I(n) <> ? the number (n) is the index for a modulus of continuity on ?I (n) if and only if ?I(n) ? Df .

PROOF. Again, the proof is essentially the same as before. We employ Proposition 8 to prove that the relation in (4) is r.e. 2

This treatment of partial functions leaves a number of open problems, e.g. the following:

ffl Is the domain of a partial computable real function a union of computable intervals? Is this union effective?
ffl The converse: Suppose f is a partial real function with an effective union of computable intervals as domain, effectively uniformly continuous on these intervals and such that f maps computable sequences to computable sequences. Is there a computable extension of f to the interval domain? Is there a largest strict extension? Is this extension computable?

5.3 Computable functions on Rn

A characterization of computable functions Rn ! R similar to Corollary 30 holds. In particular this implies that the notion coincides with Pour-El & Richards' definition [29]. The proof becomes slightly more complicated: In Theorem 26 we constructed an effective modulus of continuity by covering the interval [?m;m] with several layers" of intervals. The kth layer consisted of 2k+1 ? 1 intervals which had width 2m2k and overlap m2k . In n dimensions, we have to cover [?m;m]n by layers of n-dimensional rectangles. The edges are taken from the set of intervals from the 1-dimensional case, so there will be (2k+1 ?1)n rectangles. Width and overlap are the same as in the 1-dimensional

case. In this way, we obtain an effective construction which is more involved than for the real line.

Likewise, functions C ! R can be dealt with. Functions C ! C are split into real and imaginary part which are investigated separately.

6 Real number representations

By Corollary 19, a real number x is computable iff the set fxg is the lub of an effective ascending chain in I, that is iff it is the intersection of an effective chain of shrinking nested intervals. We now give an example of how to obtain such shrinking interval sequences.

Let us, for simplicity, consider a computable interval A. An iterated function system (IFS) on A is a finite set of computable functions fi: A ! A, i 2 K, where K is some finite indexing set. We will assume the functions to be contracting (so that the IFS is hyperbolic) and computable. Then for every total recursive function h: N ! K the sequence

J0 := A
J1 := fh(0)(A)

J2 := fh(0)(fh(1)(A))
...
Jn := fh(0)(fh(1)(? ? ? fh(n)(A) ? ? ?))
...

is a shrinking sequence of intervals and defines a computable element xh of A with fxhg = Tn2NJn. The interval Jn contains xh and is regarded as an approximation to this point.

If we further specialise this example to the IFS with A = [0; 1], K = f0; : : : ; 9g and

fi(x) = x + i
10 ; i = ; : : : ; 9;

then the sequence h(0); h(1); : : : is exactly the decimal expansion of the real number xh in the intersection of intervals. As a concrete example, take h such that h(i) is the ith decimal place of the number ss. Then

J0 := [0; 1]

J1 :=f3([0; 1]) = [0:3; :4]
J2 :=f3(f1([0; 1])) = f3([0:1; :2]) = [0:31; :32]
J3 :=f3(f1(f4([0; 1]))) = f3(f1([0:4; :5])) = f3([0:14; :15]) = [0:314; :315]
...

Note that Jn+1 is not obtained by applying fh(n) to Jn.

Similarly, expansions with respect to bases different from 10 can be expressed via IFS's. Also, one can choose the fi to have overlapping ranges, yielding various signed digit representations. For example K = f?1; ; 1g and

fi(x) = x + i
2 ; i = ?1; ; 1

for the interval A = [?1; 1] gives the signed binary expansion, where h(i) = k corresponds to digit k at the ith place.

This IFS framework can be used to represent more sophisticated number systems such as the redundant base 2 fixed-point digit-serial numbers [24], where real numbers are generated by three functions, and exact floating point [27,13] where extended real numbers are generated by the composition of one of four sign functions followed by an infinite product of digit functions chosen from a finite set of maps.

Acknowledgement

We are grateful to Mart??n H?otzel Escard?o for many fruitful discussions. Thanks to Achim Jung for helpful comments in an early stage of this work, in particular for drawing our attention to [42]. We are indebted to Viggo Stoltenberg-Hansen for making us aware of [35] and [36] after reading a previous version of this paper.

References

[1] S. Abramsky and A. Jung. Domain theory. In S. Abramsky, D.M. Gabbay, and T.S.E. Maibaum, editors, Handbook of Logic in Computer Science, volume 3, pages 1{168. Clarendon Press, 1994.

[2] E.A. Bishop and D.S. Bridges. Constructive Analysis, volume 279 of Grundlagen der mathematischen Wissenschaften. Springer Verlag, 1985.

[3] J. Blanck. Domain representability of metric spaces. Annals of Pure and Applied Logic, 83:225{247, 1997.

[4] L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers. Bulletin of the American Mathematical Society, 21:1{46, 1989.

[5] G.S. Ceitin. Algorithmic operators in constructive metric spaces. Translations of the AMS, 64:1{80, 1967.

[6] P. Di Gianantonio. A Functional Approach to Computability on Real Numbers. PhD thesis No. TD-6/93, University of Pisa-Genova-Udine, 1993.

[7] P. Di Gianantonio. Real number computability and domain theory. Information and Computation, 127(1):12{25, 1996.

[8] A. Edalat. Domains for computation in mathematics, physics and exact real arithmetic. Bulletin of Symbolic Logic. To appear.

[9] A. Edalat. When Scott is weak on the top. Math. Struct. in Comp. Science. To appear.

[10] A. Edalat. Domain theory and integration. Theoretical Computer Science, 151:163{193, 1995.

[11] A. Edalat. Dynamical systems, measures and fractals via domain theory. Information and Computation, 120(1):32{48, 1995.

[12] A. Edalat. Power domains and iterated function systems. Information and Computation, 124:182{197, 1996.

[13] A. Edalat and P. J. Potts. A new representation for exact real numbers. Electronic Notes in Theoretical Computrer Science, 6, 1997. URL: http://www.elsevier.nl/locate/entcs/volume6.html.

[14] A. Edalat and Ph. S?underhauf. Computable Banach spaces via domain theory. Manuscript in preparation.

[15] Y.L. Ershov. Computable functionals of finite type. Algebra and Logic, 11(4):203{242, 1972.

[16] M.H. Escard?o. PCF extended with real numbers. Theoretical Computer Science, 162(1):79{115, 1996.

[17] G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. W. Mislove, and D. S.

Scott. A Compendium of Continuous Lattices. Springer Verlag, Berlin, 1980.

[18] A. Grzegorczyk. Computable functionals. Fundamenta Mathematica, 42:168{ 202, 1955.

[19] A. Grzegorczyk. On the definition of computable real continuous functions. Fundamenta Mathematica, 44:61{71, 1957.

[20] Chr. Kreitz and K. Weihrauch. Theory of representaions. Theoretical Computer Science, 38:35{53, 1985.

[21] D. Lacombe. Extension de la notion de fonction r?ecursive aux fonctions d'une ou plusieurs variables r?eelles. C. R. Acad. Sci. Paris, 240:2478{2480, 241:13{14, 241:151{153, 1955.

[22] S. Mazur. Computable Analysis. PWN, Warsaw, 1963.

[23] R.E. Moore. Interval Analysis. Prentice-Hall, Englewood Cliffs, 1966.

[24] A. Nielsen and P. Kornerup. Msb-first digit serial arithmetic. JUCS, 1(7), 1995.

[25] R. Penrose. The Emperor's New Mind. Oxford University Press, 1989.

[26] G.D. Plotkin. Post-graduate lecture notes in advanced domain theory (incorporating the Pisa Notes"). Dept. of Computer Science, Univ. of Edinburgh, 1981.

[27] P. J. Potts and A. Edalat. Exact Real Computer Arithmetic, March 1997. Department of Computing Technical Report DOC 97/9, Imperial College, available from http://www-tfm.doc.ic.ac.uk/~pjp.

[28] P. J. Potts, A. Edalat, and M. H. Escard?o. Semantics of exact real arithmetic. In Proceedings of the Twelveth Annual IEEE Symposium on Logic In Computer Science, pages 248{257, Warsaw, Poland, 1997.

[29] M.B. Pour-El and J.I. Richards. Computability in Analysis and Physics. Springer Verlag, 1988.

[30] H.G. Rice. Recursive real numbers. Proceedings of the AMS, 5:784{791, 1954.

[31] H. Rogers. Theory of Recursive Functions and Effective Computability. McGraw Hill, New York, 1967.

[32] D. S. Scott. Outline of a mathematical theory of computation. In 4th Annual Princeton Conference on Information Sciences and Systems, pages 169{176, 1970.

[33] M. B. Smyth. Effectively given domains. Theoretical Computer Science, 5:257{ 274, 1977.

[34] V. Stoltenberg-Hansen, I. Lindstr?om, and E. R. Griffor. Mathematical Theory of Domains, volume 22 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1994.

[35] V. Stoltenberg-Hansen and J.V. Tucker. Complete local rings as domains. Journal of Symbolic Logic, 53:603{624, 1988.

[36] V. Stoltenberg-Hansen and J.V. Tucker. Effective algebras. In S. Abramsky, D.M. Gabbay, and T.S.E. Maibaum, editors, Handbook of Logic in Computer Science, volume 4, pages 357{526. Clarendon Press, 1995.

[37] A.M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230{265, 1937.

[38] J. E. Vuillemin. Exact real computer arithmetic with continued fractions. IEEE Transactions on Computers, 39(8):1087{1105, 1990.

[39] K. Weihrauch. Recursion and complexity theory on cpo-s. In P. Deussen, editor, Theoretical Computer Science, 5th GI-Conference, Karlsruhe, March 1981, volume 104 of Lecture Notes in Computer Science, pages 195{202. Springer Verlag, 1981.

[40] K. Weihrauch. Computability, volume 9 of EATCS Monographs on Theoretical Computer Science. Springer Verlag, 1987.

[41] K. Weihrauch. A foundation for computable analysis. In D.S. Bridges, C.S. Calude, J. Gibbons, S. Reeves, and I.H. Witten, editors, Combinatorics, Complexity, and Logic, Discrete Mathematics and Theoretical Computer Science, pages 66{89, Singapore, 1997. Springer Verlag. Proceedings of DMTCS'96.

[42] K. Weihrauch and Th. Deil. Berechenbarkeit auf cpo-s. Technical Report 63, RWTH Aachen, 1980. Schriften zur Informatik und Angewandten Mathematik.

[43] K. Weihrauch and U. Schreiber. Embedding metric spaces into cpo's. Theoretical Computer Science, 16:5{24, 1981.