page 2  (31 pages)
to previous section1
3to next section

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