2011, 29(1): 193-212. doi: 10.3934/dcds.2011.29.193

Dynamics and abstract computability: Computing invariant measures

1. 

Dipartimento di Matematica Applicata, Universita di Pisa, Italy

2. 

LORIA, Vandoeuvre-lès-Nancy, France

3. 

Fields Institute, Toronto, Canada

Received  January 2010 Revised  May 2010 Published  September 2010

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.
Citation: Stefano Galatolo, Mathieu Hoyrup, Cristóbal Rojas. Dynamics and abstract computability: Computing invariant measures. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 193-212. doi: 10.3934/dcds.2011.29.193
References:
[1]

L. Ambrosio, N. Gigli and G. Savare, Gradient flows: In metric spaces and in the space of probability measures,, in, (2005).

[2]

J. Avigad, P. Gerhardy and H. Towsner, Local stability of ergodic averages,, Transactions of the American Mathematical Society, 362 (2010), 261. doi: doi:10.1090/S0002-9947-09-04814-4.

[3]

L. Bienvenu and W. Merkle, Effective randomness for computable probability measures,, Electr. Notes Theor. Comput. Sci., 167 (2007), 117. doi: doi:10.1016/j.entcs.2006.08.010.

[4]

I. Binder, M. Braverman and M. Yampolsky, Filled Julia sets with empty interior are computable,, Journal FoCM, 7 (2007), 405.

[5]

I. Binder, M. Braverman and M. Yampolsky, On computational complexity of Siegel Julia sets,, Commun. Math. Phys., 264 (2006), 317. doi: doi:10.1007/s00220-006-1546-3.

[6]

M. L. Blank, Pathologies generated by round-off in dynamical systems,, Physica D., 78 (1994), 93. doi: doi:10.1016/0167-2789(94)00103-0.

[7]

M. L. Blank, Small perturbations of chaotic dynamical systems,, Russian Mathematical Surveys, 44 (1989), 1. doi: doi:10.1070/RM1989v044n06ABEH002302.

[8]

Vasco Brattka and Gero Presser, Computability on subsets of metric spaces,, {Theoretical Computer Science}, 305 (2003), 43. doi: doi:10.1016/S0304-3975(02)00693-X.

[9]

M. Braverman and M. Yampolsky, Non-computable Julia sets,, Journ. Amer. Math. Soc., 19 (2006), 551. doi: doi:10.1090/S0894-0347-05-00516-3.

[10]

A. A. Brudno, Entropy and the complexity of the trajectories of a dynamical system,, Trans. Mosc. Math. Soc., 44 (1983), 127.

[11]

J-R. Chazottes, P. Collet and B. Schmitt, Statistical consequences of the Devroye inequality for processes. Applications to a class of non-uniformly hyperbolic dynamical systems,, Nonlinearity, 18 (2005), 2341. doi: doi:10.1088/0951-7715/18/5/024.

[12]

P. Collins, Computability and representations of the zero set,, {Theoretical Computer Science}, 221 (2008), 37.

[13]

M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors,, Numerische Mathematik, 75 (1997), 293. doi: doi:10.1007/s002110050240.

[14]

M. Dellnitz and O. Junge, On the approximation of complicated dynamical behavior,, SIAM Journal on Numerical Analysis, 36 (1999), 491. doi: doi:10.1137/S0036142996313002.

[15]

J. Ding, Q. Du and T. Y. Li, High order approximation of the Frobenius-Perron operator,, Applied Mathematics and Computation, 53 (1993), 151. doi: doi:10.1016/0096-3003(93)90099-Z.

[16]

J. Ding and A. Zhou, The projection method for computing multidimensional absolutely continuous invariant measures,, Journal of Statistical Physics, 77 (1994), 899. doi: doi:10.1007/BF02179467.

[17]

P. Gács, Lectures notes on descriptional complexity and randomness,, Boston University, (1993), 1.

[18]

S. Galatolo, Orbit complexity by computable structures,, Nonlinearity, 13 (2000), 1531. doi: doi:10.1088/0951-7715/13/5/307.

[19]

P. Gács, M. Hoyrup and C. Rojas, Randomness on computable probability spaces-A dynamical point of view, (Susanne Albers and Jean-Yves Marion, editors),, in, (2009), 469.

[20]

S. Galatolo, M. Hoyrup and C. Rojas, A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties,, {Theor. Comput. Sci.}, 410 (2009), 2207. doi: doi:10.1016/j.tcs.2009.02.010.

[21]

S. Galatolo, M. Hoyrup and C. Rojas, Effective symbolic dynamics, random points, statistical behavior, complexity and entropy,, {Inf. Comput.}, 208 (2010), 23. doi: doi:10.1016/j.ic.2009.05.001.

[22]

S. Galatolo and M. J. Pacifico, Lorenz like flows: Exponential decay of correlations for the Poincaré map, logarithm law, quantitative recurrence,, preprint, ().

[23]

P. Hertling, Is the Mandelbrot set computable,, Math. Logic Quart, 51 (2005), 5. doi: doi:10.1002/malq.200310124.

[24]

M. Hoyrup and C. Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces,, {Inf. Comput.}, 207 (2009), 830. doi: doi:10.1016/j.ic.2008.12.009.

[25]

B. Hunt, Estimating invariant measures and Lyapunov exponents,, preprint, (1995).

[26]

S. Isola, On systems with finite ergodic degree,, Far East Journal of Dynamical Systems, 5 (2003), 1.

[27]

M. Keane, R. Murray and L. S. Young, Computing invariant measures for expanding circle maps,, Nonlinearity, 11 (1998), 27. doi: doi:10.1088/0951-7715/11/1/004.

[28]

Y. Kifer, General random perturbations of hyperbolic and expanding transformations,, Journal d'Analyse Mathématique, 47 (1986), 111. doi: doi:10.1007/BF02792535.

[29]

C. Liverani, Rigorous numerical investigations of the statistical properties of piecewise expanding maps-A feasibility study,, Nonlinearity, 14 (2001), 463. doi: doi:10.1088/0951-7715/14/3/303.

[30]

K. Palmer, "Shadowing in Dynamical Systems-Theory and Applications. Mathematics and its Applications," 501,, Kluwer Academic Publishers, (2000).

[31]

M. Pollicott and O. Jenkinson, Computing invariant densities and metric entropy,, Comm. Math. Phys., 211 (2000), 687. doi: doi:10.1007/s002200050832.

[32]

H. Rogers, "Theory of Recursive Functions and Effective Computability,", MIT Press Cambridge, (1987).

[33]

S. G. Simpson, "Subsystems of Second Order Arithmetic,", Perspectives in Mathematical Logic, (1999).

[34]

W. Tucker, The Lorenz attractor exists,, C. R. Acad. Sci. Paris, 328 (1999), 1197.

[35]

A. Turing, On computable numbers, with an application to the Entscheidungsproblem,, Proc. Lond. Math. Soc. 2, 42 (1936), 230.

[36]

M. Viana, "Stochastic Dynamics of Deterministic Systems,", Brazillian Math, (1997).

[37]

L. S. Young, What are SRB measures, and which dynamical systems have them?,, Journal of Statistical Physics, 108 (2002), 733. doi: doi:10.1023/A:1019762724717.

[38]

K. Weihrauch, "A Simple Introduction to Computable Analysis,", Technical Report 171 7-1995, (1995), 7.

[39]

K. Weihrauch, "Computable Analysis. An Introduction,", Springer, (2000).

show all references

References:
[1]

L. Ambrosio, N. Gigli and G. Savare, Gradient flows: In metric spaces and in the space of probability measures,, in, (2005).

[2]

J. Avigad, P. Gerhardy and H. Towsner, Local stability of ergodic averages,, Transactions of the American Mathematical Society, 362 (2010), 261. doi: doi:10.1090/S0002-9947-09-04814-4.

[3]

L. Bienvenu and W. Merkle, Effective randomness for computable probability measures,, Electr. Notes Theor. Comput. Sci., 167 (2007), 117. doi: doi:10.1016/j.entcs.2006.08.010.

[4]

I. Binder, M. Braverman and M. Yampolsky, Filled Julia sets with empty interior are computable,, Journal FoCM, 7 (2007), 405.

[5]

I. Binder, M. Braverman and M. Yampolsky, On computational complexity of Siegel Julia sets,, Commun. Math. Phys., 264 (2006), 317. doi: doi:10.1007/s00220-006-1546-3.

[6]

M. L. Blank, Pathologies generated by round-off in dynamical systems,, Physica D., 78 (1994), 93. doi: doi:10.1016/0167-2789(94)00103-0.

[7]

M. L. Blank, Small perturbations of chaotic dynamical systems,, Russian Mathematical Surveys, 44 (1989), 1. doi: doi:10.1070/RM1989v044n06ABEH002302.

[8]

Vasco Brattka and Gero Presser, Computability on subsets of metric spaces,, {Theoretical Computer Science}, 305 (2003), 43. doi: doi:10.1016/S0304-3975(02)00693-X.

[9]

M. Braverman and M. Yampolsky, Non-computable Julia sets,, Journ. Amer. Math. Soc., 19 (2006), 551. doi: doi:10.1090/S0894-0347-05-00516-3.

[10]

A. A. Brudno, Entropy and the complexity of the trajectories of a dynamical system,, Trans. Mosc. Math. Soc., 44 (1983), 127.

[11]

J-R. Chazottes, P. Collet and B. Schmitt, Statistical consequences of the Devroye inequality for processes. Applications to a class of non-uniformly hyperbolic dynamical systems,, Nonlinearity, 18 (2005), 2341. doi: doi:10.1088/0951-7715/18/5/024.

[12]

P. Collins, Computability and representations of the zero set,, {Theoretical Computer Science}, 221 (2008), 37.

[13]

M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors,, Numerische Mathematik, 75 (1997), 293. doi: doi:10.1007/s002110050240.

[14]

M. Dellnitz and O. Junge, On the approximation of complicated dynamical behavior,, SIAM Journal on Numerical Analysis, 36 (1999), 491. doi: doi:10.1137/S0036142996313002.

[15]

J. Ding, Q. Du and T. Y. Li, High order approximation of the Frobenius-Perron operator,, Applied Mathematics and Computation, 53 (1993), 151. doi: doi:10.1016/0096-3003(93)90099-Z.

[16]

J. Ding and A. Zhou, The projection method for computing multidimensional absolutely continuous invariant measures,, Journal of Statistical Physics, 77 (1994), 899. doi: doi:10.1007/BF02179467.

[17]

P. Gács, Lectures notes on descriptional complexity and randomness,, Boston University, (1993), 1.

[18]

S. Galatolo, Orbit complexity by computable structures,, Nonlinearity, 13 (2000), 1531. doi: doi:10.1088/0951-7715/13/5/307.

[19]

P. Gács, M. Hoyrup and C. Rojas, Randomness on computable probability spaces-A dynamical point of view, (Susanne Albers and Jean-Yves Marion, editors),, in, (2009), 469.

[20]

S. Galatolo, M. Hoyrup and C. Rojas, A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties,, {Theor. Comput. Sci.}, 410 (2009), 2207. doi: doi:10.1016/j.tcs.2009.02.010.

[21]

S. Galatolo, M. Hoyrup and C. Rojas, Effective symbolic dynamics, random points, statistical behavior, complexity and entropy,, {Inf. Comput.}, 208 (2010), 23. doi: doi:10.1016/j.ic.2009.05.001.

[22]

S. Galatolo and M. J. Pacifico, Lorenz like flows: Exponential decay of correlations for the Poincaré map, logarithm law, quantitative recurrence,, preprint, ().

[23]

P. Hertling, Is the Mandelbrot set computable,, Math. Logic Quart, 51 (2005), 5. doi: doi:10.1002/malq.200310124.

[24]

M. Hoyrup and C. Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces,, {Inf. Comput.}, 207 (2009), 830. doi: doi:10.1016/j.ic.2008.12.009.

[25]

B. Hunt, Estimating invariant measures and Lyapunov exponents,, preprint, (1995).

[26]

S. Isola, On systems with finite ergodic degree,, Far East Journal of Dynamical Systems, 5 (2003), 1.

[27]

M. Keane, R. Murray and L. S. Young, Computing invariant measures for expanding circle maps,, Nonlinearity, 11 (1998), 27. doi: doi:10.1088/0951-7715/11/1/004.

[28]

Y. Kifer, General random perturbations of hyperbolic and expanding transformations,, Journal d'Analyse Mathématique, 47 (1986), 111. doi: doi:10.1007/BF02792535.

[29]

C. Liverani, Rigorous numerical investigations of the statistical properties of piecewise expanding maps-A feasibility study,, Nonlinearity, 14 (2001), 463. doi: doi:10.1088/0951-7715/14/3/303.

[30]

K. Palmer, "Shadowing in Dynamical Systems-Theory and Applications. Mathematics and its Applications," 501,, Kluwer Academic Publishers, (2000).

[31]

M. Pollicott and O. Jenkinson, Computing invariant densities and metric entropy,, Comm. Math. Phys., 211 (2000), 687. doi: doi:10.1007/s002200050832.

[32]

H. Rogers, "Theory of Recursive Functions and Effective Computability,", MIT Press Cambridge, (1987).

[33]

S. G. Simpson, "Subsystems of Second Order Arithmetic,", Perspectives in Mathematical Logic, (1999).

[34]

W. Tucker, The Lorenz attractor exists,, C. R. Acad. Sci. Paris, 328 (1999), 1197.

[35]

A. Turing, On computable numbers, with an application to the Entscheidungsproblem,, Proc. Lond. Math. Soc. 2, 42 (1936), 230.

[36]

M. Viana, "Stochastic Dynamics of Deterministic Systems,", Brazillian Math, (1997).

[37]

L. S. Young, What are SRB measures, and which dynamical systems have them?,, Journal of Statistical Physics, 108 (2002), 733. doi: doi:10.1023/A:1019762724717.

[38]

K. Weihrauch, "A Simple Introduction to Computable Analysis,", Technical Report 171 7-1995, (1995), 7.

[39]

K. Weihrauch, "Computable Analysis. An Introduction,", Springer, (2000).

[1]

Vieri Benci, C. Bonanno, Stefano Galatolo, G. Menconi, M. Virgilio. Dynamical systems and computable information. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 935-960. doi: 10.3934/dcdsb.2004.4.935

[2]

Radosław Kurek, Paweł Lubowiecki, Henryk Żołądek. The Hess-Appelrot system. Ⅲ. Splitting of separatrices and chaos. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 1955-1981. doi: 10.3934/dcds.2018079

[3]

Shi Jin, Christof Sparber, Zhennan Zhou. On the classical limit of a time-dependent self-consistent field system: Analysis and computation. Kinetic & Related Models, 2017, 10 (1) : 263-298. doi: 10.3934/krm.2017011

[4]

Marta Lewicka, Piotr B. Mucha. A local existence result for a system of viscoelasticity with physical viscosity. Evolution Equations & Control Theory, 2013, 2 (2) : 337-353. doi: 10.3934/eect.2013.2.337

[5]

Elzbieta Ratajczyk, Urszula Ledzewicz, Maciej Leszczyński, Heinz Schättler. Treatment of glioma with virotherapy and TNF-α inhibitors: Analysis as a dynamical system. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 425-441. doi: 10.3934/dcdsb.2018029

[6]

Leonardi Filippo. A projection method for the computation of admissible measure valued solutions of the incompressible Euler equations. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : 941-961. doi: 10.3934/dcdss.2018056

[7]

Sébastien Court. Stabilization of a fluid-solid system, by the deformation of the self-propelled solid. Part II: The nonlinear system.. Evolution Equations & Control Theory, 2014, 3 (1) : 83-118. doi: 10.3934/eect.2014.3.83

[8]

Sébastien Court. Stabilization of a fluid-solid system, by the deformation of the self-propelled solid. Part I: The linearized system.. Evolution Equations & Control Theory, 2014, 3 (1) : 59-82. doi: 10.3934/eect.2014.3.59

[9]

Tomasz Szarek, Mariusz Urbański, Anna Zdunik. Continuity of Hausdorff measure for conformal dynamical systems. Discrete & Continuous Dynamical Systems - A, 2013, 33 (10) : 4647-4692. doi: 10.3934/dcds.2013.33.4647

[10]

Paweł Lubowiecki, Henryk Żołądek. The Hess-Appelrot system. I. Invariant torus and its normal hyperbolicity. Journal of Geometric Mechanics, 2012, 4 (4) : 443-467. doi: 10.3934/jgm.2012.4.443

[11]

Mingyong Lai, Hongming Yang, Songping Yang, Junhua Zhao, Yan Xu. Cyber-physical logistics system-based vehicle routing optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 701-715. doi: 10.3934/jimo.2014.10.701

[12]

Avner Friedman, Bei Hu, Chuan Xue. A three dimensional model of wound healing: Analysis and computation. Discrete & Continuous Dynamical Systems - B, 2012, 17 (8) : 2691-2712. doi: 10.3934/dcdsb.2012.17.2691

[13]

Yuting Ding, Jinli Xu, Jun Cao, Dongyan Zhang. Mathematical modeling about nonlinear delayed hydraulic cylinder system and its analysis on dynamical behaviors. Discrete & Continuous Dynamical Systems - S, 2017, 10 (5) : 943-958. doi: 10.3934/dcdss.2017049

[14]

Patrick Fischer, Charles-Henri Bruneau, Hamid Kellay. Multiresolution analysis for 2D turbulence. part 2: A physical interpretation. Discrete & Continuous Dynamical Systems - B, 2007, 7 (4) : 717-734. doi: 10.3934/dcdsb.2007.7.717

[15]

Nasab Yassine. Quantitative recurrence of some dynamical systems preserving an infinite measure in dimension one. Discrete & Continuous Dynamical Systems - A, 2018, 38 (1) : 343-361. doi: 10.3934/dcds.2018017

[16]

P.K. Newton. The dipole dynamical system. Conference Publications, 2005, 2005 (Special) : 692-699. doi: 10.3934/proc.2005.2005.692

[17]

Salvador Addas-Zanata. A simple computable criteria for the existence of horseshoes. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 365-370. doi: 10.3934/dcds.2007.17.365

[18]

Dorota Bors, Robert Stańczy. Dynamical system modeling fermionic limit. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 45-55. doi: 10.3934/dcdsb.2018004

[19]

Xiangnan He, Wenlian Lu, Tianping Chen. On transverse stability of random dynamical system. Discrete & Continuous Dynamical Systems - A, 2013, 33 (2) : 701-721. doi: 10.3934/dcds.2013.33.701

[20]

Jianfeng Feng, Mariya Shcherbina, Brunello Tirozzi. Dynamical behaviour of a large complex system. Communications on Pure & Applied Analysis, 2008, 7 (2) : 249-265. doi: 10.3934/cpaa.2008.7.249

2017 Impact Factor: 1.179

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (2)

[Back to Top]