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

• Undecidability in Rn: Riddled Basins, the KAM Tori and the Stability of the Solar System [PDF] Philosophy of Science 70 (2003) pp. 359-382

...

1. Introduction. Several authors have suggested that the long-term behavior of some deterministic physical systems, or of some classical models in Rn , is in some sense uncomputable (Moore 1990, 1991; Moser 1978, 67– 68; Pitowsky 1996; Sommerer and Ott 1996; Wolfram 1985). At their most explicit, these authors argue that the set of real-valued states leading eventually to a certain kind of behavior is undecidable. However, none of these authors gives a rigorous definition of decidability for sets of real-valued states, and this warrants more concern than one might expect. Intuitively, a set is decidable if there is a mechanical procedure that will always determine whether or not a given object in the domain of discourse is in that set. For sets of natural numbers, this intuitive notion seems to be captured by the rigorous mathematical concept of a “recursive” set, and this concept is nontrivial in extension. That is, there are many recursive sets of natural numbers and many nonrecursive ones (setting aside any constructivistic denial of nonrecursive sets). For sets of real numbers or real n-tuples, however, there is no uniquely standard notion of a decidable set. There is a standard notion of a computable function on the reals or real n-tuples, called Grzegorczyk-computability, with many different formulations (Grzegorczyk 1955a, b, 1957; Ko 1991; Pour-El and Caldwell 1975; Pour-El and Richards 1983; Weihrauch 2000), but it does not directly suggest a useful concept of a decidable set of reals. One might like to say that a set B of reals is decidable if the characteristic function of B (i.e., vB(x)
1 if x
B, vB(x)
0 otherwise) is Grzegorczyck-computable. However, this notion is practically unsatisfi- able. Grzegorczyk-computable functions are always continuous (Grzegorczyk 1955a), but in Rn , only
and Rn have continuous characteristic functions.1 Hence in the obvious sense for sets of real n-tuples, undecidability is trivial