Effective metric spaces and representations of the reals
Based on standard notions of classical recursion theory, a natural model of approximate computability for partial functions between effective metric spaces is presented. It generalizes the Ko-Friedman approach to computability of real functions by means of oracle Turing machines, follows the main ideas of Weihrauch's type 2 theory of effectivity, but it avoids the explicit use of representations. The topological arithmetical hierarchy is introduced and shown to be strict if the underlying space contains an effectively discrete sequence. The domains of computable functions are exactly the Pi(2)-sets of this hierarchy if the space admits a finitary stratification. Finally, this framework is used to investigate and characterize the standard representations of the real numbers. They are just those functions from the name space onto the reals which have both computable extensions and inversions that are computable as relations. (C) 2002 Elsevier Science B.V. All rights reserved.
effective metric space approximate computability oracle turing machine topological arithmetical hierarchy domains of computable functions standard representation representation of the real numbers computable analysis