Three concepts of decidability for general subsets of uncountable spaces

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


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.



External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.


Added to PP

36,919 (#34)

6 months
385 (#852)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Matthew Parker
London School of Economics

References found in this work

No references found.

Add more references