|  | |||||||||
Expanding the text here will generate a large
amount of data for your browser to display
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