Dynamical systems: unpredictability vs incomputability.

The long-term forecasting of chaotic dynamical systems is generally not possible, because of the so-called "sensitivity to initial conditions": if you do not know exactly the initial state of a system, you cannot predict its long-range evolution. For this reason, the mathematical theory of dynamical systems is more focused on the understanding of the global, asymptotic behaviour of dynamical systems than the prediction of individual trajectories. In particular, several notions of entropies of a system are defined in order to quantify its unpredictability.

Computability theory provides another perspective on the problem of unpredictability: a system is unpredictable if its evolution cannot be computed by a machine. Unpredictability is then understood as incomputability, or difficulty to compute.

I will present some works that connect these two approaches: the classical one from the mathematical theory of dynamical systems, the recursion-theoretic one using concepts from computability theory, especially Kolmogorov complexity.

Retrieved from http://www.lix.polytechnique.fr/~bournez/PC2009/i.php/Main/MathieuHoyrup

Page last modified on August 04, 2009, at 03:02 PM