Abstract
Our aim is to discover whether the notion of algorithmic orbit-complexity can serve to define “chaos” in a dynamical system. We begin with a mostly expository discussion of algorithmic complexity and certain results of Brudno, Pesin, and Ruelle (BRP theorems) which relate the degree of exponential instability of a dynamical system to the average algorithmic complexity of its orbits. When one speaks of predicting the behavior of a dynamical system, one usually has in mind one or more variables in the phase space that are of particular interest. To say that the system is unpredictable is, roughly, to say that one cannot feasibly determine future values of these variables from an approximation of the initial conditions of the system. We introduce the notions of restrictedexponential instability and conditionalorbit-complexity, and announce a new and rather general result, similar in spirit to the BRP theorems, establishing average conditional orbit-complexity as a lower bound for the degree of restricted exponential instability in a dynamical system. The BRP theorems require the phase space to be compact and metrizable. We construct a noncompact kicked rotor dynamical system of physical interest, and show that the relationship between orbit-complexity and exponential instability fails to hold for this system. We conclude that orbit-complexity cannot serve as a general definition of “chaos.”
Similar content being viewed by others
References
Robert W. Batterman, “Chaos, quantization, and the correspondence principle,”Synthese 89, 189–227 (1991).
Robert W. Batterman, “Defining chaos,”Philos. Sci. 60, 43–66 (1993).
Robert W. Batterman, Quantum chaos and semiclassical mechanics. InPSA 1992 (Philosophy of Science Association. 1993). Vol. 2, pp. 50–65.
Robert W. Batterman, “Theories between theories: Asymptotic limiting intertheoretic relations,”Synthese 103, 171–201 (1995).
Robert W. Batterman, Chaos: Algorithmic complexity vs. dynamical instability, inProceedings, (1994)Conference on Law and Prediction in (Natural) Science in the Light of Our New Knowledge from Chaos Research (Internationales Forschungszentrum fur Grundfragen der Wissenschaften, Salzburg, Austria), forthcoming.
M. Brin and A. Katok, “On local entropy,” in J. Palis Jr., ed..Geometric Dynamics (Vol. 1007,Lecture Notes in Mathematics) (Springer, Berlin, 1983), pp. 30–38.
A. A. Brudno, “Entropy and the complexity of the trajectories of a dynamical system.”Trans. Moscow Math. Soc. (2), 127–151 (1983).
Boris V. Chirikov, “A universal instability of many dimensional oscillator systems,”Phys. Rep. 52, 263–379 (1979).
J. Ford, G. Mantica, and G. H. Ristow, “The Arnol'd cat: Failure of the correspondence principle,”Physica D 50, 493–520 (1991).
Joseph Ford, “Quantum chaos, is there any?” in H. Bai-Lin, ed.,Directions in Chaos (World Scientific, Singapore. 1988), Vol. 2, pp. 128–147.
Joseph Ford, “What is chaos, that we should be mindful of it?” in P. Davies, ed.The New Physics (Cambridge University Press, Cambridge, 1989), pp. 348–371.
Ya. B. Pesin, “Characteristic Lyapunov exponents and smooth ergodic theory,”Russ. Math. Surv. 32(4), 55–144 (1977).
Karl Petersen,Ergodic Theory (Cambridge University Press, Cambridge, 1983).
Homer White, “On the Algorithmic Complexity of the Trajectories of Points in Dynamical Systems,” PhD thesis, University of North Carolina-Chapel Hill, 1991.
Homer White, “Algorithmic complexity of points in dynamical systems,”Ergodic Theory Dynam. Syst. 13 807–830 (1993).
Homer White, “Conditional algorithmic complexity and restricted exponential instability in measure-preserving systems,” Technical report. University of Kentucky, Department of Statistics, 1995.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Batterman, R.W., White, H. Chaos and algorithmic complexity. Found Phys 26, 307–336 (1996). https://doi.org/10.1007/BF02069475
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02069475