Three concepts of decidability for general subsets of uncountable spaces

Theoretical Computer Science 351 (1):2-13 (2003)

Authors
Matthew Parker
London School of Economics
Abstract
There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: R.S. Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rn and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rn with the standard measure, it is strictly stronger than r.a. [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent.
Keywords Computable analysis  Recursive sets  Recursively approximable sets  Undecidability
Categories (categorize this paper)
Reprint years 2006
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Recursive Constructions in Topological Spaces.Iraj Kalantari & Allen Retzlaff - 1979 - Journal of Symbolic Logic 44 (4):609-625.
Recursively Enumerable Generic Sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
The Ordertype of Β-R.E. Sets.Klaus Sutner - 1990 - Journal of Symbolic Logic 55 (2):573-576.
Finite Powers of Strong Measure Zero Sets.Marion Scheepers - 1999 - Journal of Symbolic Logic 64 (3):1295-1306.
An Invariance Notion in Recursion Theory.Robert E. Byerly - 1982 - Journal of Symbolic Logic 47 (1):48-66.
Sets and Point-Sets: Five Grades of Set-Theoretic Involvement in Geometry.John P. Burgess - 1988 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:456 - 463.
Properties of Ideals on the Generalized Cantor Spaces.Jan Kraszewski - 2001 - Journal of Symbolic Logic 66 (3):1303-1320.

Analytics

Added to PP index
2012-04-20

Total views
29,290 ( #29 of 2,289,680 )

Recent downloads (6 months)
5,866 ( #19 of 2,289,680 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature