Recursive and Computable Operations over Topological Structures

Vasco Brattka

We present a definition of recursive multi-valued operations over topological structures (which include structures for the real numbers and other spaces used in analysis).

One of the main results states that over a certain class of structures, so-called perfect structures, recursive operations coincide with computable operations, as defined via Turing machines in computable analysis [2]. Moreover, by a Stability Theorem, perfect structures uniquely characterize their own computability theory.

We propose a general method to derive perfect structures from recursive metric spaces and we exhibit this method for a number of general hyper and function spaces which play an important role in computable analysis.

Finally, we define classes of recursive sets over structures and we show that these notions are generalizations of the classical notions from recursion theory and computable analysis.

[1] Vasco  Brattka,  Recursive  and  Computable  Operations  over  Topolog-
ical  Spaces,  PhD  Thesis,  FernUniversität  Hagen,  1999,  available:

    www.informatik.fernuni-hagen.de/thi1/vasco.brattka/thesis/

[2] Klaus Weihrauch, An Introduction to Computable Analysis, Springer, Berlin, 2000

Address: Theoretische Informatik I, FernUniversität Hagen, D-58084 Hagen, Germany

E-mail: vasco.brattka@fernuni-hagen.de