
A domaintheoretic 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 StoltenbergHansen 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 Turingmachine based approach which dates back to Grzegorczyk and Lacombe, is used by PourEl & 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 ndimensional Euclidean space.
1 Introduction
Computable analysis is traditionally approached from two different directions. On the one hand, we have the machineoriented 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 BlumShubSmale model [4] can also be considered as machineoriented. Real numbers are regarded as entities, but the computable functions are constructed from building blocks in a recursiontheoretic manner.
On the other hand, we have the analysisoriented 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 Turingmachine computable real functions as those that map computable sequences to computable sequences and are effectively uniformly continuous. The work of PourEl & Richards [29] is based on this definition and is now wellestablished 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 socalled algebraic domains to model functional programming languages has become a wellestablished 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. StoltenbergHansen 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], StoltenbergHansen & 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 PourEl & 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 socalled 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 machinebased 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 wellestablished 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 domaintheoretic notions for computable real numbers and for computable functions coincide with the wellestablished socalled Polish approach which dates back to Grzegorczyk and Lacombe [18,21] and is equivalent to the above mentioned TTEapproach and to the definitions of PourEl & 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 PourEl & 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 socalled 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 selfcontained 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 ndimensional Euclidean space and the complex plane.
To be selfcontained, 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 5XVIII]. 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 nonempty 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 waybelow 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 nonnegative
reals [0; 1] with the usual ordering form a continuous domain.
The Scotttopology 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 Scottopen. Moreover, they form a basis for the topology. A function f : (D; v) ! (E; v) between dcpo's is continuous with respect to the Scotttopologies 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 Scottcontinuous 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 Scottopen 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 Scottcontinuous 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 Scotttopology 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 Scotttopology on the product coincides with the product topology of the Scotttopologies on the factors. Unlike the situation in general topology, it is true that a function f : D ? D0 ! E is Scottcontinuous if and only if it is Scottcontinuous in both variables separately. This is due to the fact that Scottcontinuity can be characterised purely in ordertheoretical 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 waybelow 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 nonzero 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 Scotttopology 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 Scotttopology 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 Scotttopology is homeomorphic to the real line via fxg 7! x.
Every continuous function f : R ! R has a Scottcontinuous extension to the interval domain. This means that there is a Scottcontinuous 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 nonbottom 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 welldefined.
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 Scotttopology 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 wellknown 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 ochain, 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 nonempty 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 ochain. 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 ochain, it is possible to effectively obtain an effective ochain 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 waybelow the supremum is the union of the sets of elements waybelow 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 MyhillShepherdsonTheorem 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 Scottcontinuous 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 boundedcomplete 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 nonempty 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 boundedcomplete.
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 waybelow 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 leftcomputable and y is rightcomputable.
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 rightcomputable." 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 Cauchysequences 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 wellknown 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 01 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 ntuples 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 ndimensional 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 inclusionintheinterior. 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 ntupling 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 ndimensional case. Occurrences of the absolute value jxj have to be replaced (where appropriate) by, for example, the 1norm
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 Scotttopology 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 reformulation of [19] which PourEl and Richards employ as a starting point for a detailed treatment of computable analysis [29].
Definition 24 A function f : R ! R is PRcomputable 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 Scottcontinuous 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 PRcomputable.
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 PRcomputable functions. PourEl 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 PRcomputable 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
welldefined. 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 PRcomputable function is computable.
PROOF. Suppose f : R ! R is PRcomputable. 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 PRcomputable.
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 BanachMazur [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 PRcomputable 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 PourEl & 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 ndimensional rectangles. The edges are taken from the set of intervals from the 1dimensional case, so there will be (2k+1 ?1)n rectangles. Width and overlap are the same as in the 1dimensional
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 fixedpoint digitserial 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 StoltenbergHansen 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. TD6/93, University of PisaGenovaUdine, 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. PrenticeHall, Englewood Cliffs, 1966.
[24] A. Nielsen and P. Kornerup. Msbfirst digit serial arithmetic. JUCS, 1(7), 1995.
[25] R. Penrose. The Emperor's New Mind. Oxford University Press, 1989.
[26] G.D. Plotkin. Postgraduate 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://wwwtfm.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. PourEl 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. StoltenbergHansen, 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. StoltenbergHansen and J.V. Tucker. Complete local rings as domains. Journal of Symbolic Logic, 53:603{624, 1988.
[36] V. StoltenbergHansen 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 cpos. In P. Deussen, editor, Theoretical Computer Science, 5th GIConference, 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 cpos. 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.