Theoretical Computer Science 351 (1):2-13 (2003)
AbstractThere 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.
Similar books and articles
Undecidability in Rn: Riddled Basins, the KAM Tori, and the Stability of the Solar System.Matthew W. Parker - 2003 - Philosophy of Science 70 (2):359-382.
Recursive Constructions in Topological Spaces.Iraj Kalantari & Allen Retzlaff - 1979 - Journal of Symbolic Logic 44 (4):609-625.
Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices.Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman - 1996 - Journal of Symbolic Logic 61 (3):880-905.
Construction of Models for Algebraically Generalized Recursive Function Theory.H. R. Strong - 1970 - Journal of Symbolic Logic 35 (3):401-409.
Recursively Enumerable Generic Sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
Splitting Theorems for Speed-Up Related to Order of Enumeration.A. M. Dawes - 1982 - Journal of Symbolic Logic 47 (1):1-7.
Finite Powers of Strong Measure Zero Sets.Marion Scheepers - 1999 - Journal of Symbolic Logic 64 (3):1295-1306.
On Consistent Subsets of Large Sets of Satisfiable Sentences.Stephen H. Hechler - 2001 - Studia Logica 69 (3):339-349.
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.
Decidability and ℵ0-Categoricity of Theories of Partially Ordered Sets.James H. Schmerl - 1980 - Journal of Symbolic Logic 45 (3):585 - 611.
Properties of Ideals on the Generalized Cantor Spaces.Jan Kraszewski - 2001 - Journal of Symbolic Logic 66 (3):1303-1320.
Added to PP
Historical graph of downloads
Citations of this work
Philosophical Method and Galileo's Paradox of Infinity.Matthew W. Parker - 2008 - In Bart Van Kerkhove (ed.), New Perspectives on Mathematical Practices: Essays in Philosophy and History of Mathematics : Brussels, Belgium, 26-28 March 2007. World Scientfic.
Computing the Uncomputable; or, The Discrete Charm of Second-Order Simulacra.Matthew W. Parker - 2009 - Synthese 169 (3):447-463.
References found in this work
No references found.