Dynamics and abstract computability: Computing invariant measures
Open Access
- 1 January 2011
- journal article
- Published by American Institute of Mathematical Sciences (AIMS) in Discrete and Continuous Dynamical Systems
- Vol. 31 (1) , 193-212
Abstract
We consider the question of computing invariant measures from an abstract point of view. Here, computing a measure means finding an algorithm which can output descriptions of the measure up to any precision. We work in a general framework (computable metric spaces) where this problem can be posed precisely. We will find invariant measures as fixed points of the transfer operator. In this case, a general result ensures the computability of isolated fixed points of a computable map. We give general conditions under which the transfer operator is computable on a suitable set. This implies the computability of many "regular enough" invariant measures and among them many physical measures. On the other hand, not all computable dynamical systems have a computable invariant measure. We exhibit two examples of computable dynamics, one having a physical measure which is not computable and one for which no invariant measure is computable, showing some subtlety in this kind of problems.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Effective symbolic dynamics, random points, statistical behavior, complexity and entropyInformation and Computation, 2010
- Lorenz-like flows: exponential decay of correlations for the Poincaré map, logarithm law, quantitative recurrenceErgodic Theory and Dynamical Systems, 2009
- Computability and Representations of the Zero SetElectronic Notes in Theoretical Computer Science, 2008
- Filled Julia Sets with Empty Interior Are ComputableFoundations of Computational Mathematics, 2006
- Statistical consequences of the Devroye inequality for processes. Applications to a class of non-uniformly hyperbolic dynamical systemsNonlinearity, 2005
- Computable Analysis2000
- The Lorenz attractor existsComptes Rendus de l'Académie des Sciences - Series I - Mathematics, 1999
- Subsystems of Second Order Arithmetic1999
- Theory of Recursive Functions and Effective Computability.The American Mathematical Monthly, 1969
- On Computable Numbers, with an Application to the EntscheidungsproblemProceedings of the London Mathematical Society, 1937