Computability on subsets of metric spaces

✍ Scribed by Vasco Brattka; Gero Presser

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 524 KB
• Volume: 305
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00693-x

✦ Synopsis

The notions "recursively enumerable" and "recursive" are the basic notions of e ectivity in classical recursion theory. In computable analysis, these notions are generalized to closed subsets of Euclidean space using their metric distance functions. We study a further generalization of these concepts to subsets of computable metric spaces. It appears that di erent characterizations, which coincide in case of Euclidean space, lead to di erent notions in the general case. However, under certain additional conditions, such as completeness and e ective local compactness, the situation is similar to the Euclidean case. We present all results in the framework of "Type-2 Theory of E ectivity" which allows to express e ectivity properties in a very uniform way: instead of comparing properties of single subsets, we compare corresponding representations of the hyperspace of closed subsets. Such representations do not only induce a concept of computability for single subsets, but they even yield a concept of computability for operations on hyperspaces, such as union, intersection, etc. We complete our investigation by studying the special situation of compact subsets.