Dissertation, University of Chicago (2005)
AbstractThe behavior of some systems is non-computable in a precise new sense. One infamous problem is that of the stability of the solar system: Given the initial positions and velocities of several mutually gravitating bodies, will any eventually collide or be thrown off to infinity? Many have made vague suggestions that this and similar problems are undecidable: no finite procedure can reliably determine whether a given configuration will eventually prove unstable. But taken in the most natural way, this is trivial. The state of a system corresponds to a point in a continuous space, and virtually no set of points in space is strictly decidable. A new, more pragmatic concept is therefore introduced: a set is decidable up to measure zero (d.m.z.) if there is a procedure to decide whether a point is in that set and it only fails on some points that form a set of zero volume. This is motivated by the intuitive correspondence between volume and probability: we can ignore a zero-volume set of states because the state of an arbitrary system almost certainly will not fall in that set. D.m.z. is also closer to the intuition of decidability than other notions in the literature, which are either less strict or apply only to special sets, like closed sets. Certain complicated sets are not d.m.z., most remarkably including the set of known stable orbits for planetary systems (the KAM tori). This suggests that the stability problem is indeed undecidable in the precise sense of d.m.z. Carefully extending decidability concepts from idealized models to actual systems, we see that even deterministic aspects of physical behavior can be undecidable in a clear and significant sense.
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.
Dynamic Topological Logic Interpreted Over Minimal Systems.David Fernández-Duque - 2011 - Journal of Philosophical Logic 40 (6):767-804.
Three Concepts of Decidability for General Subsets of Uncountable Spaces.Matthew W. Parker - 2003 - Theoretical Computer Science 351 (1):2-13.
Long-Term Behavior in the Theory of Moves.Stephen J. Willson - 1998 - Theory and Decision 45 (3):201-240.
Undecidable Semiassociative Relation Algebras.Roger D. Maddux - 1994 - Journal of Symbolic Logic 59 (2):398-418.
Comments on `Two Undecidable Problems of Analysis'.Bruno Scarpellini - 2003 - Minds and Machines 13 (1):79-85.
Undecidable Relativizations of Algebras of Relations.Szabolcs Mikulás & Maarten Marx - 1999 - Journal of Symbolic Logic 64 (2):747-760.
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.
Truth in V for Ǝ ∀∀-Sentences Is Decidable.D. Bellé & F. Parlamento - 2006 - Journal of Symbolic Logic 71 (4):1200 - 1222.
Decidable Subspaces and Recursively Enumerable Subspaces.C. J. Ash & R. G. Downey - 1984 - Journal of Symbolic Logic 49 (4):1137-1145.
A Decidable Variety That is Finitely Undecidable.Joohee Jeong - 1999 - Journal of Symbolic Logic 64 (2):651-677.
Decidable and Undecidable Logics with a Binary Modality.ágnes Kurucz, István Németi, Ildikó Sain & András Simon - 1995 - Journal of Logic, Language and Information 4 (3):191-206.
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.