Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T16:00:26.129Z Has data issue: false hasContentIssue false
  • English
  • Français

Undecidability in Rn: Riddled Basins, the KAM Tori, and the Stability of the Solar System

Published online by Cambridge University Press:  01 January 2022

Matthew W. Parker
Get access Rights & Permissions [Opens in a new window]

Abstract

Some have suggested that certain classical physical systems have undecidable long-term behavior, without specifying an appropriate notion of decidability over the reals. We introduce such a notion, decidability in μ (or d-μ) for any measure μ, which is particularly appropriate for physics and in some ways more intuitive than Ko's (1991) recursive approximability (r.a.). For Lebesgue measure λ, d-λ implies r.a. Sets with positive λ-measure that are sufficiently “riddled” with holes are never d-λ but are often r.a. This explicates Sommerer and Ott's (1996) claim of uncomputable behavior in a system with riddled basins of attraction. Furthermore, it clarifies speculations that the stability of the solar system (and similar systems) may be undecidable, for the invariant tori established by KAM theory form sets that are not d-λ.

Type
Research Article
Information
Philosophy of Science , Volume 70 , Issue 2 , April 2003 , pp. 359 - 382
Copyright
Copyright © The Philosophy of Science Association

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

‡

I thank Wayne Myrvold, Howard Stein, William Wimsatt, Greg Lavers, Matthew Frank, Eric Schliesser, James Meiss, Norman Leibowitz, John Sommerer, Cristopher Moore, Jim Guszcza, Jill North, Amit Hagar, Joan Wackerman, David Malament, and the referees for comments on this and related efforts, the University of Western Ontario for the opportunity to present this research, Waid Parker for financial support, and Laurel Parker.

References

Alexander, J.C., Yorke, James A., You, Zhiping, and Kan, Ittai (1992), “Riddled Basins”, Riddled Basins 2:795–813.Google Scholar
Arnol’d, Vladimir I. (1963a), “Proof of a Theorem of A.N. Kolmogorov on the Invariance of Quasi-Periodic Motions Under Small Perturbations of the Hamiltonian”, Proof of a Theorem of A.N. Kolmogorov on the Invariance of Quasi-Periodic Motions Under Small Perturbations of the Hamiltonian 18:9–36.Google Scholar
Arnol’d, Vladimir I. (1963b), “Small Denominators and Problems of Stability of Motion in Classical and Celestial Mechanics”, Small Denominators and Problems of Stability of Motion in Classical and Celestial Mechanics 18:85–191.Google Scholar
Arnol’d, Vladimir I. (1964), “Instability of Dynamical Systems with Several Degrees of Freedom”, Instability of Dynamical Systems with Several Degrees of Freedom 5:581–585.Google Scholar
Batterman, Robert W. (1998), “Why Equilibrium Statistical Mechanics Works: Universality and the Renormalization Group”, Why Equilibrium Statistical Mechanics Works: Universality and the Renormalization Group 65:183–208Google Scholar
Blum Lenore, Mike Shub, and Smale, Steve (1989), “On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions, and Universal Machines”, On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions, and Universal Machines 21:1–46.Google Scholar
Davis, Martin D., and Weyuker, Elaine J. (1983), Computability, Complexity, and Languages. San Diego, CA: Academic Press.Google Scholar
De la Llave, Rafael (2001), “A Tutorial on KAM Theory”, Mathematical Physics Archive (01–29), http://www.ma.utexas.edu/mp_arc/index-01.html.Google Scholar
Diacu, Florin, and Holmes, Philip (1996), Celestial Encounters: The Origins of Chaos and Stability. Princeton: Princeton University Press.Google Scholar
Gödel, Kurt (1931), “Über Formal Unenterscheidbare Städer Principia Mathematica und verwandter Systeme I”, Über Formal Unenterscheidbare Städer Principia Mathematica und verwandter Systeme I 38:173–198. Translated in Kurt Gödel (1986), Collected Works I. Oxford: Oxford University Press.Google Scholar
Goroff, Daniel L. (1993), Introduction to New Methods of Celestial Mechanics by Henri Poincaré. Woodbury, NY: American Institute of Physics.Google Scholar
Grzegorczyk, A. (1955a), “Computable Functionals”, Computable Functionals 42:169–202.Google Scholar
Grzegorczyk, A. (1955b), “On the Definition of Computable Functionals”, On the Definition of Computable Functionals 42:233–239.Google Scholar
Grzegorczyk, A. (1957), “On the Definitions of Computable Real Continuous Functions”, On the Definitions of Computable Real Continuous Functions 44:61–67.Google Scholar
Heagy, James F., Carroll, Thomas L., and Pecora, Louis M. (1994), “Experimental and Numerical Evidence for Riddled Basins in Coupled Chaotic Systems”, Experimental and Numerical Evidence for Riddled Basins in Coupled Chaotic Systems 73:3528–3531.Google ScholarPubMed
Ko, Ker-I (1991), Complexity Theory of Real Functions. Boston: Birkhauser.CrossRefGoogle Scholar
Malament, David, and Zabell, Sandy (1980), “Why Gibbs Phase Averages Work—The Role of Ergodic Theory”, Why Gibbs Phase Averages Work—The Role of Ergodic Theory 47:339–349.Google Scholar
Milnor, John (1985), “On the Concept of Attractor”, On the Concept of Attractor 99:177–195.Google Scholar
Moore, Cristopher (1990), “Unpredictability and Undecidability in Dynamical Systems”, Unpredictability and Undecidability in Dynamical Systems 64:2354–2357.Google ScholarPubMed
Moore, Cristopher (1991), “Generalized Shifts: Unpredictability and Undecidability in Dynamical Systems”, Generalized Shifts: Unpredictability and Undecidability in Dynamical Systems 4:199–230.Google Scholar
Moser, Jürgen (1973), Stable and Random Motions in Dynamical Systems. Princeton: Princeton University Press.Google Scholar
Moser, Jürgen (1978), “Is the Solar System Stable?”, Is the Solar System Stable? 1:65–71.Google Scholar
Myrvold, Wayne C. (1997), “The Decision Problem for Entaglement,” in Cohen, R.S. et al. (eds.), Potentiality, Entanglement, and Passion-at-a-Distance. Great Britain: Kluwer Academic Publishers, 177–190.CrossRefGoogle Scholar
Ott Edward, J.C. Alexander, Kan, Ittai, Sommerer, John C., and Yorke, James A. (1994), “The Transition to Chaotic Attractors with Riddled Basins”, The Transition to Chaotic Attractors with Riddled Basins 76: 384.Google Scholar
Parker, Matthew W. (1998), “Did Poincaré Really Discover Chaos?”, Did Poincaré Really Discover Chaos? 29, 578–588.Google Scholar
Pitowsky, Itamar (1996), “Laplace’s Demon Consults an Oracle: The Computational Complexity of Prediction”, Laplace’s Demon Consults an Oracle: The Computational Complexity of Prediction 27:161–180.Google Scholar
Poincaré, Henri (1890), “Sur le Problème des Trois Corps et les Équations de la Dynamique”, Sur le Problème des Trois Corps et les Équations de la Dynamique 13:1–270.Google Scholar
Poincaré, Henri (1891), “Le Problème des Trois Corps”, Le Problème des Trois Corps 2 (1): 1–5..Google Scholar
Poincaré, Henri (1898), “On the Stability of the Solar System”, On the Stability of the Solar System 58: 183.Google Scholar
Poincaré, Henri (1907) “Le Hasard”, Le Hasard 3:257–276. Translated in Henri Poincaré (1952), Science and Method. New York: Dover Publications, Inc.Google Scholar
Poincaré, Henri ([1892–1899] 1993) New Methods of Celestial Mechanics. Reprint. Woodbury, NY: American Institute of Physics. Originally published as Les Méthodes Nouvelles de la Méchanique Céleste.Google Scholar
Jürgen, Pöschel (1982) “Integrability of Hamiltonian Systems on Cantor Sets”, Integrability of Hamiltonian Systems on Cantor Sets 35:653–695.Google Scholar
Pour-El, Marian Boykan, and Caldwell, Jerome (1975), “On a Simple Definition of Computable Function of a Real Variable—With Application to Functions of a Complex Variable”, On a Simple Definition of Computable Function of a Real Variable—With Application to Functions of a Complex Variable 21:1–19.Google Scholar
Pour-El, Marian Boykan, and Richards, Ian (1983), “Computability and Noncomputability in Classical Analysis,” Trans. Am. Math. Soc. 275:539–545.CrossRefGoogle Scholar
Sklar, Lawrence (1973), “Statistical Explanation and Ergodic Theory”, Statistical Explanation and Ergodic Theory 40:194–212.Google Scholar
Sklar, Lawrence (1993), Physics and Chance. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Soare, Robert I. (1987), Recursively Enumerable Sets and Degrees. New York: Springer-Verlag.CrossRefGoogle Scholar
Sommerer, John C., and Ott, Edward (1993), “A Physical System with Qualitatively Uncertain Dynamics”, A Physical System with Qualitatively Uncertain Dynamics 365:138–140.Google Scholar
Sommerer, John C., and Ott, Edward (1996), “Intermingled Basins of Attraction: Uncomputability in a Simple Physical System”, Intermingled Basins of Attraction: Uncomputability in a Simple Physical System A 214:243–251. Figure reprinted with permission from Elsevier Science, Copyright 1996.Google Scholar
Turing, Alan (1936), “On Computable Numbers with an Application to the Entscheidungsproblem”, On Computable Numbers with an Application to the Entscheidungsproblem 42:230–265.Google Scholar
Vranas, Peter B.M. (1998), “Epsilon-Ergodicity and the Success of Equilibrium Statistical Mechanics”, Epsilon-Ergodicity and the Success of Equilibrium Statistical Mechanics 65:688–708.Google Scholar
Weihrauch, Klaus (2000), Computable Analysis. Berlin: Springer-Verlag.10.1007/978-3-642-56999-9CrossRefGoogle Scholar
Wolfram, Stephen (1985), “Undecidability and Intractability in Theoretical Physics”, Undecidability and Intractability in Theoretical Physics 54:735–738.Google ScholarPubMed