Dynamics and abstract computability: computing invariant measures
Authors:
- Stefano GalatoloSGStefano Galatolo
- Mathieu HoyrupMHMathieu Hoyrup
- Cristobal RojasCRCristobal Rojas
Preprint
Abstract
We consider the question of computing invariant measures from an abstract point of view. We work in a general framework (computable metric spaces, computable measures and functions) where this problem can be posed precisely. We consider invariant measures as fixed points of the transfer operator and give general conditions under which the transfer operator is (sufficiently) computable. In this case, a general result ensures the computability of isolated fixed points and hence invariant measures (in given classes of "regular" measures). This implies the computability of many SRB measures. On the other hand, not all computable dynamical systems have a computable invariant measure. We exhibit two interesting examples of computable dynamics, one having an SRB measure which is not computable and another having no computable invariant measure at all, showing some subtlety in this kind of problems.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Effective symbolic dynamics, random points, statistical behavior, complexity and entropyInformation and Computation, 2010
- A constructive Borel–Cantelli lemma. Constructing orbits with required statistical propertiesTheoretical Computer Science, 2009
- Effective Randomness for Computable Probability MeasuresElectronic Notes in Theoretical Computer Science, 2007
- Filled Julia Sets with Empty Interior Are ComputableFoundations of Computational Mathematics, 2006
- On Computational Complexity of Siegel Julia SetsCommunications in Mathematical Physics, 2006
- Computability on subsets of metric spacesTheoretical Computer Science, 2003
- Computing Invariant Densities and Metric EntropyCommunications in Mathematical Physics, 2000
- The projection method for computing multidimensional absolutely continuous invariant measuresJournal of Statistical Physics, 1994
- Pathologies generated by round-off in dynamical systemsPhysica D: Nonlinear Phenomena, 1994
- High order approximation of the Frobenius-Perron operatorApplied Mathematics and Computation, 1993