A domain-theoretic approach to computable analysis
by
Philipp Sünderhauf
Department of Computing, Imperial College London
Coauthors: Abbas Edalat

In recent years, there has been a considerable amount of work on using domain theory 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.

The aim of this work is to provide a precise formulation of the domain-theoretic approach to real numbers and show that this approach is equivalent to the other, well-established, work in real number computability.

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 that our approach to real number computability is equivalent to the established Turing-machine based approach which dates back to Grzegorczyk and Lacombe and is used by Pour-El & Richards in their foundational work on computable analysis.

The domain-theoretic framework also makes it possible to consider computability on metric spaces and Banach spaces. Again, the domain-theoretic computability theory is equivalent to the approach by Pour-El & Richards which is the agreed notion of computability among Physisits as can be seen in the work of Penrose.

Date received: June 30, 1997

Copyright © 1997 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caao-58.