|
|
Computability over Topological Structures
Vasco Brattka, in: S. Barry Cooper and Sergey S. Goncharov (eds.),
Computability and Models, Kluwer Academic Publishers, New-York, 2003, 93--136
Abstract
Computable analysis is the Turing machine based theory of computability
on the real numbers and other topological spaces.
Similarly as Ershov's concept of numberings can be used to deal with
discrete structures, Kreitz and Weihrauch's concept of representations
can be used to handle structures of continuum cardinality.
In this context the choice of representations is
very sensitively related to the underlying notion of approximation, hence
to topology. In this paper we summarize some basic ideas of the representation
based approach to computable analysis and we introduce an abstract and purely
set theoretic characterization of this theory which can be considered
as a generalization of the classical concept of µ-recursive functions.
Together with this characterization we introduce the notion of a perfect
topological structure. In particular, these structures are effectively categorical,
i.e. they characterize their own computability theory.
Important examples of perfect structures are provided by metric spaces
and additional attention is paid to their effective subsets.
Electronical Versions (March 15, 2002)