Computability over Topological Structures

Computable analysis is the Turing machine based theory of computability on the real numbers and other topological spaces. Similarly as Eršov’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.