Chaos and algorithmic complexity

Foundations of Physics 26 (3):307-336 (1996)


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.”

Download options


    Upload a copy of this work     Papers currently archived: 72,856

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

25 (#461,226)

6 months
1 (#386,040)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Robert W. Batterman
University of Pittsburgh

References found in this work

Defining Chaos.Robert W. Batterman - 1993 - Philosophy of Science 60 (1):43-66.

Add more references

Citations of this work

What Are the New Implications of Chaos for Unpredictability?Charlotte Werndl - 2009 - British Journal for the Philosophy of Science 60 (1):195-220.
Entropy - A Guide for the Perplexed.Roman Frigg & Charlotte Werndl - 2011 - In Claus Beisbart & Stephan Hartmann (eds.), Probabilities in Physics. Oxford University Press. pp. 115-142.
Randomness Is Unpredictability.Antony Eagle - 2005 - British Journal for the Philosophy of Science 56 (4):749-790.
Chaos Out of Order: Quantum Mechanics, the Correspondence Principle and Chaos.Gordon Belot & John Earman - 1997 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 28 (2):147-182.

View all 6 citations / Add more citations

Similar books and articles