# American Institute of Mathematical Sciences

January  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 and Continuous Dynamical Systems, 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 "Lectures in Mathematics ETH Zürich," Birkhäuser Verlag, Basel, (2005). [2] J. Avigad, P. Gerhardy and H. Towsner, Local stability of ergodic averages, Transactions of the American Mathematical Society, 362 (2010), 261-288. 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-130. 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-416. [5] I. Binder, M. Braverman and M. Yampolsky, On computational complexity of Siegel Julia sets, Commun. Math. Phys., 264 (2006), 317-334. 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-114. 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-33. doi: doi:10.1070/RM1989v044n06ABEH002302. [8] Vasco Brattka and Gero Presser, Computability on subsets of metric spaces, Theoretical Computer Science, 305 (2003), 43-76. 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-578. 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-151. [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-2364. 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-43. [13] M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors, Numerische Mathematik, 75 (1997), 293-317. 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-515. 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-171. 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-908. doi: doi:10.1007/BF02179467. [17] P. Gács, Lectures notes on descriptional complexity and randomness, Boston University, 1993, 1-67. [18] S. Galatolo, Orbit complexity by computable structures, Nonlinearity, 13 (2000), 1531-1546. 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 "26th International Symposium on Theoretical Aspects of Computer Science," (STACS 2009), 469-480. [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-2222. 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-41. 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, arXiv:arXiv:0901.0574 (to appear on Erg. Th. Dyn. Sys: doi: 10.1017/S0143385709000856). [23] P. Hertling, Is the Mandelbrot set computable, Math. Logic Quart, 51 (2005), 5-18. 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-847. doi: doi:10.1016/j.ic.2008.12.009. [25] B. Hunt, Estimating invariant measures and Lyapunov exponents, preprint, http://www.chaos.umd.edu/ bhunt/research/eimale.pdf, 1995. [26] S. Isola, On systems with finite ergodic degree, Far East Journal of Dynamical Systems, 5 (2003), 1-62. [27] M. Keane, R. Murray and L. S. Young, Computing invariant measures for expanding circle maps, Nonlinearity, 11 (1998), 27-46. 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-150. 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-490. 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, Dordrecht, 2000. [31] M. Pollicott and O. Jenkinson, Computing invariant densities and metric entropy, Comm. Math. Phys., 211 (2000), 687-703. doi: doi:10.1007/s002200050832. [32] H. Rogers, "Theory of Recursive Functions and Effective Computability," MIT Press Cambridge, MA, USA, 1987. [33] S. G. Simpson, "Subsystems of Second Order Arithmetic," Perspectives in Mathematical Logic, Springer-Verlag, Cambridge University Press, 1999. [34] W. Tucker, The Lorenz attractor exists, C. R. Acad. Sci. Paris, 328 (1999), 1197-1202. [35] A. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc. 2, 42 (1936), 230-265. [36] M. Viana, "Stochastic Dynamics of Deterministic Systems," Brazillian Math, IMPA, Colloquium 1997. [37] L. S. Young, What are SRB measures, and which dynamical systems have them?, Journal of Statistical Physics, 108 (2002), 733-754. doi: doi:10.1023/A:1019762724717. [38] K. Weihrauch, "A Simple Introduction to Computable Analysis," Technical Report 171 7-1995, FernUniversitat, 1995. [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 "Lectures in Mathematics ETH Zürich," Birkhäuser Verlag, Basel, (2005). [2] J. Avigad, P. Gerhardy and H. Towsner, Local stability of ergodic averages, Transactions of the American Mathematical Society, 362 (2010), 261-288. 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-130. 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-416. [5] I. Binder, M. Braverman and M. Yampolsky, On computational complexity of Siegel Julia sets, Commun. Math. Phys., 264 (2006), 317-334. 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-114. 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-33. doi: doi:10.1070/RM1989v044n06ABEH002302. [8] Vasco Brattka and Gero Presser, Computability on subsets of metric spaces, Theoretical Computer Science, 305 (2003), 43-76. 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-578. 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-151. [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-2364. 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-43. [13] M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors, Numerische Mathematik, 75 (1997), 293-317. 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-515. 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-171. 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-908. doi: doi:10.1007/BF02179467. [17] P. Gács, Lectures notes on descriptional complexity and randomness, Boston University, 1993, 1-67. [18] S. Galatolo, Orbit complexity by computable structures, Nonlinearity, 13 (2000), 1531-1546. 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 "26th International Symposium on Theoretical Aspects of Computer Science," (STACS 2009), 469-480. [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-2222. 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-41. 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, arXiv:arXiv:0901.0574 (to appear on Erg. Th. Dyn. Sys: doi: 10.1017/S0143385709000856). [23] P. Hertling, Is the Mandelbrot set computable, Math. Logic Quart, 51 (2005), 5-18. 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-847. doi: doi:10.1016/j.ic.2008.12.009. [25] B. Hunt, Estimating invariant measures and Lyapunov exponents, preprint, http://www.chaos.umd.edu/ bhunt/research/eimale.pdf, 1995. [26] S. Isola, On systems with finite ergodic degree, Far East Journal of Dynamical Systems, 5 (2003), 1-62. [27] M. Keane, R. Murray and L. S. Young, Computing invariant measures for expanding circle maps, Nonlinearity, 11 (1998), 27-46. 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-150. 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-490. 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, Dordrecht, 2000. [31] M. Pollicott and O. Jenkinson, Computing invariant densities and metric entropy, Comm. Math. Phys., 211 (2000), 687-703. doi: doi:10.1007/s002200050832. [32] H. Rogers, "Theory of Recursive Functions and Effective Computability," MIT Press Cambridge, MA, USA, 1987. [33] S. G. Simpson, "Subsystems of Second Order Arithmetic," Perspectives in Mathematical Logic, Springer-Verlag, Cambridge University Press, 1999. [34] W. Tucker, The Lorenz attractor exists, C. R. Acad. Sci. Paris, 328 (1999), 1197-1202. [35] A. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc. 2, 42 (1936), 230-265. [36] M. Viana, "Stochastic Dynamics of Deterministic Systems," Brazillian Math, IMPA, Colloquium 1997. [37] L. S. Young, What are SRB measures, and which dynamical systems have them?, Journal of Statistical Physics, 108 (2002), 733-754. doi: doi:10.1023/A:1019762724717. [38] K. Weihrauch, "A Simple Introduction to Computable Analysis," Technical Report 171 7-1995, FernUniversitat, 1995. [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 and 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 and Continuous Dynamical Systems, 2018, 38 (4) : 1955-1981. doi: 10.3934/dcds.2018079 [3] Marta Lewicka, Piotr B. Mucha. A local existence result for a system of viscoelasticity with physical viscosity. Evolution Equations and Control Theory, 2013, 2 (2) : 337-353. doi: 10.3934/eect.2013.2.337 [4] Shi Jin, Christof Sparber, Zhennan Zhou. On the classical limit of a time-dependent self-consistent field system: Analysis and computation. Kinetic and Related Models, 2017, 10 (1) : 263-298. doi: 10.3934/krm.2017011 [5] Sébastien Court. Stabilization of a fluid-solid system, by the deformation of the self-propelled solid. Part II: The nonlinear system.. Evolution Equations and Control Theory, 2014, 3 (1) : 83-118. doi: 10.3934/eect.2014.3.83 [6] Sébastien Court. Stabilization of a fluid-solid system, by the deformation of the self-propelled solid. Part I: The linearized system.. Evolution Equations and Control Theory, 2014, 3 (1) : 59-82. doi: 10.3934/eect.2014.3.59 [7] Leonardi Filippo. A projection method for the computation of admissible measure valued solutions of the incompressible Euler equations. Discrete and Continuous Dynamical Systems - S, 2018, 11 (5) : 941-961. doi: 10.3934/dcdss.2018056 [8] Elzbieta Ratajczyk, Urszula Ledzewicz, Maciej Leszczyński, Heinz Schättler. Treatment of glioma with virotherapy and TNF-α inhibitors: Analysis as a dynamical system. Discrete and Continuous Dynamical Systems - B, 2018, 23 (1) : 425-441. doi: 10.3934/dcdsb.2018029 [9] 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 [10] Mingyong Lai, Hongming Yang, Songping Yang, Junhua Zhao, Yan Xu. Cyber-physical logistics system-based vehicle routing optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 701-715. doi: 10.3934/jimo.2014.10.701 [11] Avner Friedman, Bei Hu, Chuan Xue. A three dimensional model of wound healing: Analysis and computation. Discrete and Continuous Dynamical Systems - B, 2012, 17 (8) : 2691-2712. doi: 10.3934/dcdsb.2012.17.2691 [12] Tomasz Szarek, Mariusz Urbański, Anna Zdunik. Continuity of Hausdorff measure for conformal dynamical systems. Discrete and Continuous Dynamical Systems, 2013, 33 (10) : 4647-4692. doi: 10.3934/dcds.2013.33.4647 [13] Yuting Ding, Jinli Xu, Jun Cao, Dongyan Zhang. Mathematical modeling about nonlinear delayed hydraulic cylinder system and its analysis on dynamical behaviors. Discrete and Continuous Dynamical Systems - S, 2017, 10 (5) : 943-958. doi: 10.3934/dcdss.2017049 [14] Qi Yang, Lei Wang, Enmin Feng, Hongchao Yin, Zhilong Xiu. Identification and robustness analysis of nonlinear hybrid dynamical system of genetic regulation in continuous culture. Journal of Industrial and Management Optimization, 2020, 16 (2) : 579-599. doi: 10.3934/jimo.2018168 [15] Patrick Fischer, Charles-Henri Bruneau, Hamid Kellay. Multiresolution analysis for 2D turbulence. part 2: A physical interpretation. Discrete and Continuous Dynamical Systems - B, 2007, 7 (4) : 717-734. doi: 10.3934/dcdsb.2007.7.717 [16] Mohammad Akil, Haidar Badawi. The influence of the physical coefficients of a Bresse system with one singular local viscous damping in the longitudinal displacement on its stabilization. Evolution Equations and Control Theory, 2022  doi: 10.3934/eect.2022004 [17] Nasab Yassine. Quantitative recurrence of some dynamical systems preserving an infinite measure in dimension one. Discrete and Continuous Dynamical Systems, 2018, 38 (1) : 343-361. doi: 10.3934/dcds.2018017 [18] P.K. Newton. The dipole dynamical system. Conference Publications, 2005, 2005 (Special) : 692-699. doi: 10.3934/proc.2005.2005.692 [19] Salvador Addas-Zanata. A simple computable criteria for the existence of horseshoes. Discrete and Continuous Dynamical Systems, 2007, 17 (2) : 365-370. doi: 10.3934/dcds.2007.17.365 [20] Ruchika Sehgal, Aparna Mehra. Worst-case analysis of Gini mean difference safety measure. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1613-1637. doi: 10.3934/jimo.2020037

2021 Impact Factor: 1.588