×

Approximate decidability in Euclidean spaces. (English) Zbl 1024.03045

The author studies concepts of decidability for subsets of \({\mathbb R}^n\) within the framework of approximate computability theory in the sense of C. Kreitz and K. Weihrauch [Lect. Notes Comput. Sci. 145, 165-174 (1982; Zbl 0501.03025)]. He proposes and studies a new notion of approximate decidability which is an effective version of Hausdorff’s concept of resolvable set. The notion modifies and generalizes the notions of recursivity from computable analysis, formerly used for open and closed sets only, to more general types of sets. He shows how approximate decidability of sets can be equivalently expressed in terms of computability of the characteristic functions by means of appropriately working oracle Turing machines. It is shown how analogs of \(m\)-reducibility for subsets of \({\mathbb R}^n\) can be defined and studied in the framework of resolvability and approximate decidability.

MSC:

03D80 Applications of computability and recursion theory
03D45 Theory of numerations, effectively presented structures
03F60 Constructive and recursive analysis
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
26E40 Constructive real analysis
03D10 Turing machines and related notions

Citations:

Zbl 0501.03025
PDFBibTeX XMLCite
Full Text: DOI