July  2020, 40(7): 4259-4286. doi: 10.3934/dcds.2020180

Computability of topological entropy: From general systems to transformations on Cantor sets and the interval

1. 

Center for sleep and consciousness, University of Wisconsin-Madison, WI, United States

2. 

Departamento de Matemáticas, Universidad Andres Bello, República 498, Santiago, Chile

3. 

Institut de Mathématiques de Toulouse, Université Paul Sabatier, 118 route de Narbonne, F-3106214 Toulouse Cedex 9, France

Received  June 2019 Published  April 2020

Fund Project: Cristobal Rojas was partially supported by the European Union's Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 731143, by project FONDECYT Regular No 1190493 and project Basal PFB-03 CMM-Universidad de Chile.
Mathieu Sablik is supported by the Labex CIMI project "Computational Complexity of Dynamical Systems".

The dynamics of symbolic systems, such as multidimensional subshifts of finite type or cellular automata, are known to be closely related to computability theory. In particular, the appropriate tools to describe and classify topological entropy for this kind of systems turned out to be algorithmic. Part of the great importance of these symbolic systems relies on the role they have played in understanding more general systems over non-symbolic spaces. The aim of this article is to investigate topological entropy from a computability point of view in this more general, not necessarily symbolic setting. In analogy to effective subshifts, we consider computable maps over effective compact sets in general metric spaces, and study the computability properties of their topological entropies. We show that even in this general setting, the entropy is always a $ \Sigma_2 $-computable number. We then study how various dynamical and analytical constrains affect this upper bound, and prove that it can be lowered in different ways depending on the constraint considered. In particular, we obtain that all $ \Sigma_2 $-computable numbers can already be realized within the class of surjective computable maps over $ \{0,1\}^{{\mathbb N}} $, but that this bound decreases to $ \Pi_{1} $(or upper)-computable numbers when restricted to expansive maps. On the other hand, if we change the geometry of the ambient space from the symbolic $ \{0,1\}^{{\mathbb N}} $ to the unit interval $ [0,1] $, then we find a quite different situation – we show that the possible entropies of computable systems over $ [0,1] $ are exactly the $ \Sigma_{1} $(or lower)-computable numbers and that this characterization switches down to precisely the computable numbers when we restrict the class of system to the quadratic family.

Citation: Silvére Gangloff, Alonso Herrera, Cristobal Rojas, Mathieu Sablik. Computability of topological entropy: From general systems to transformations on Cantor sets and the interval. Discrete & Continuous Dynamical Systems - A, 2020, 40 (7) : 4259-4286. doi: 10.3934/dcds.2020180
References:
[1]

R. L. AdlerA. G. Konheim and M. H. McAndrew, Topological entropy, Trans. Amer. Math. Soc., 114 (1965), 309-319.  doi: 10.1090/S0002-9947-1965-0175106-9.  Google Scholar

[2]

N. Aubrun and M. Sablik, Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Appl. Math., 126 (2013), 35-63.  doi: 10.1007/s10440-013-9808-5.  Google Scholar

[3]

I. BinderM. BravermanC. Rojas and M. Yampolsky, Computability of Brolin-Lyubich measure, Comm. Math. Phys., 308 (2011), 743-771.  doi: 10.1007/s00220-011-1363-1.  Google Scholar

[4]

V. Brattka, P. Hertling and K. Weihrauch, A tutorial on computable analysis, in New Computational Paradigms, Springer, New York, 2008. doi: 10.1007/978-0-387-68546-5_18.  Google Scholar

[5]

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

[6]

M. Braverman, C. Rojas and J. Schneider, Space-bounded church-turing thesis and computational tractability of closed systems, Physical Review Letters, 115 (2015), 098701. doi: 10.1103/PhysRevLett.115.098701.  Google Scholar

[7]

M. A. BurrM. Schmoll and C. Wolf, On the computability of rotation sets and their entropies, Ergodic Theory Dynam. Systems, 40 (2020), 367-401.  doi: 10.1017/etds.2018.45.  Google Scholar

[8]

T. S. CubittD. Perez-Garcia and M. M. Wolf, Undecidability of the spectral gap, Nature, 528 (2015), 207-211.  doi: 10.1038/nature16059.  Google Scholar

[9]

M. Denker, C. Grillenberger and K. Sigmund, Ergodic Theory on Compact Spaces, Vol. 527, Lecture Notes in Mathematics, Springer-Verlag, Berlin-New York, 1976.  Google Scholar

[10] R. L. Devaney, An Introduction to Chaotic Dynamical Systems, Westview Press, Boulder, CO, 2003.   Google Scholar
[11]

A. Douady, Topological entropy of unimodal maps: Monotonicity for quadratic polynomials, in Real and Complex Dynamical Systems, Vol. 464, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Kluwer Acad. Publ., Dordrecht, 1995.  Google Scholar

[12]

A. Dudko and M. Yampolsky, Almost every real quadratic polynomial has a poly-time computable Julia set, Found. Comp. Math., 18 (2018), 1233-1243.  doi: 10.1007/s10208-017-9367-7.  Google Scholar

[13]

A. J. Dunlop and M. B. Pour-El, The degree of unsolvability of a real number, in Computability and Complexity in Analysis (eds. J. Blanck, V. Brattka and P. Hertling), Vol. 2064, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 2001. doi: 10.1007/3-540-45335-0_2.  Google Scholar

[14]

S. GalatoloM. Hoyrup and C. Rojas, Dynamics and abstract computability: Computing invariant measures, Discrete Contin. Dyn. Syst., 29 (2011), 193-212.  doi: 10.3934/dcds.2011.29.193.  Google Scholar

[15]

S. Gangloff and B. H. de Menibus, Effect of quantified irreducibility on computability of subshifts entropy, Discrete Contin. Dyn. Syst., 39 (2019), 1975-2000.  doi: 10.3934/dcds.2019083.  Google Scholar

[16]

D. S. Graça, C. Rojas and N. Zhong, Computing geometric Lorenz attractors with arbitrary precision, Trans. Amer. Math. Soc., 370 (2018), 2955–2970. doi: 10.1090/tran/7228.  Google Scholar

[17]

J. Graczyk and G. Światek, Generic hyperbolicity in the logistic family, Ann. of Math., 146 (1997), 1-52.  doi: 10.2307/2951831.  Google Scholar

[18]

P. Guillon and C. Zinoviadis, Densities and entropies in cellular automata, in How the World Computes, Vol. 7318, Lecture Notes in Comput. Sci., Springer, Heidelberg, 2012. doi: 10.1007/978-3-642-30870-3_26.  Google Scholar

[19]

M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167.  doi: 10.1007/s00222-008-0161-7.  Google Scholar

[20]

L. P. HurdJ. Kari and K. Culik, The topological entropy of cellular automata is uncomputable, Ergodic Theory Dynam. Systems, 12 (1992), 255-265.  doi: 10.1017/S0143385700006738.  Google Scholar

[21]

E. Jeandel, Computability of the entropy of one-tape Turing machines, in 31$^st$ International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2014.  Google Scholar

[22]

A. Katok and B. Hasselblatt, Introduction to the Modern Theory of Dynamical Systems, Vol. 54, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511809187.  Google Scholar

[23]

A. Kawamura, H. Thies and M. Ziegler, Average-case polynomial-time computability of Hamiltonian dynamics, in 43rd International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.  Google Scholar

[24]

K.-I. Ko, Complexity Theory of Real Functions. Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1991. doi: 10.1007/978-1-4684-6802-1.  Google Scholar

[25]

P. Koiran, The topological entropy of iterated piecewise affine maps is uncomputable, Discrete Math. Theor. Comput. Sci., 4 (2001), 351-356.   Google Scholar

[26]

P. Kůrka, On topological dynamics of Turing machines, Theoret. Comput. Sci., 174 (1997), 203-216.  doi: 10.1016/S0304-3975(96)00025-4.  Google Scholar

[27]

J. Milnor, Is entropy effectively computable?, Semantic Scholar, (2002). Google Scholar

[28]

M. Misiurewicz and W. Szlenk, Entropy of piecewise monotone mappings, Studia Math., 67 (1977), 45-63.  doi: 10.4064/sm-67-1-45-63.  Google Scholar

[29]

C. Moore, Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett., 64 (1990), 2354-2357.  doi: 10.1103/PhysRevLett.64.2354.  Google Scholar

[30]

S. Ruette, Chaos on the interval - a survey of relationship between the various kinds of chaos for continuous interval maps, preprint, arXiv: 1504.03001 Google Scholar

[31]

C. Spandl, Computing the topological entropy of shifts, MLQ Math. Log. Q., 53 (2007), 493-510.  doi: 10.1002/malq.200710014.  Google Scholar

[32]

G. Swiatek, Hyperbolicity is dense in the real quadratic family, preprint, arXiv: math/9207219. Google Scholar

[33]

X. Zheng and K. Weihrauch, The arithmetical hierarchy of real numbers, MLQ Math. Log. Q., 47 (2001), 51-65.  doi: 10.1002/1521-3870(200101)47:1<51::AID-MALQ51>3.0.CO;2-W.  Google Scholar

show all references

References:
[1]

R. L. AdlerA. G. Konheim and M. H. McAndrew, Topological entropy, Trans. Amer. Math. Soc., 114 (1965), 309-319.  doi: 10.1090/S0002-9947-1965-0175106-9.  Google Scholar

[2]

N. Aubrun and M. Sablik, Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Appl. Math., 126 (2013), 35-63.  doi: 10.1007/s10440-013-9808-5.  Google Scholar

[3]

I. BinderM. BravermanC. Rojas and M. Yampolsky, Computability of Brolin-Lyubich measure, Comm. Math. Phys., 308 (2011), 743-771.  doi: 10.1007/s00220-011-1363-1.  Google Scholar

[4]

V. Brattka, P. Hertling and K. Weihrauch, A tutorial on computable analysis, in New Computational Paradigms, Springer, New York, 2008. doi: 10.1007/978-0-387-68546-5_18.  Google Scholar

[5]

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

[6]

M. Braverman, C. Rojas and J. Schneider, Space-bounded church-turing thesis and computational tractability of closed systems, Physical Review Letters, 115 (2015), 098701. doi: 10.1103/PhysRevLett.115.098701.  Google Scholar

[7]

M. A. BurrM. Schmoll and C. Wolf, On the computability of rotation sets and their entropies, Ergodic Theory Dynam. Systems, 40 (2020), 367-401.  doi: 10.1017/etds.2018.45.  Google Scholar

[8]

T. S. CubittD. Perez-Garcia and M. M. Wolf, Undecidability of the spectral gap, Nature, 528 (2015), 207-211.  doi: 10.1038/nature16059.  Google Scholar

[9]

M. Denker, C. Grillenberger and K. Sigmund, Ergodic Theory on Compact Spaces, Vol. 527, Lecture Notes in Mathematics, Springer-Verlag, Berlin-New York, 1976.  Google Scholar

[10] R. L. Devaney, An Introduction to Chaotic Dynamical Systems, Westview Press, Boulder, CO, 2003.   Google Scholar
[11]

A. Douady, Topological entropy of unimodal maps: Monotonicity for quadratic polynomials, in Real and Complex Dynamical Systems, Vol. 464, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Kluwer Acad. Publ., Dordrecht, 1995.  Google Scholar

[12]

A. Dudko and M. Yampolsky, Almost every real quadratic polynomial has a poly-time computable Julia set, Found. Comp. Math., 18 (2018), 1233-1243.  doi: 10.1007/s10208-017-9367-7.  Google Scholar

[13]

A. J. Dunlop and M. B. Pour-El, The degree of unsolvability of a real number, in Computability and Complexity in Analysis (eds. J. Blanck, V. Brattka and P. Hertling), Vol. 2064, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 2001. doi: 10.1007/3-540-45335-0_2.  Google Scholar

[14]

S. GalatoloM. Hoyrup and C. Rojas, Dynamics and abstract computability: Computing invariant measures, Discrete Contin. Dyn. Syst., 29 (2011), 193-212.  doi: 10.3934/dcds.2011.29.193.  Google Scholar

[15]

S. Gangloff and B. H. de Menibus, Effect of quantified irreducibility on computability of subshifts entropy, Discrete Contin. Dyn. Syst., 39 (2019), 1975-2000.  doi: 10.3934/dcds.2019083.  Google Scholar

[16]

D. S. Graça, C. Rojas and N. Zhong, Computing geometric Lorenz attractors with arbitrary precision, Trans. Amer. Math. Soc., 370 (2018), 2955–2970. doi: 10.1090/tran/7228.  Google Scholar

[17]

J. Graczyk and G. Światek, Generic hyperbolicity in the logistic family, Ann. of Math., 146 (1997), 1-52.  doi: 10.2307/2951831.  Google Scholar

[18]

P. Guillon and C. Zinoviadis, Densities and entropies in cellular automata, in How the World Computes, Vol. 7318, Lecture Notes in Comput. Sci., Springer, Heidelberg, 2012. doi: 10.1007/978-3-642-30870-3_26.  Google Scholar

[19]

M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167.  doi: 10.1007/s00222-008-0161-7.  Google Scholar

[20]

L. P. HurdJ. Kari and K. Culik, The topological entropy of cellular automata is uncomputable, Ergodic Theory Dynam. Systems, 12 (1992), 255-265.  doi: 10.1017/S0143385700006738.  Google Scholar

[21]

E. Jeandel, Computability of the entropy of one-tape Turing machines, in 31$^st$ International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2014.  Google Scholar

[22]

A. Katok and B. Hasselblatt, Introduction to the Modern Theory of Dynamical Systems, Vol. 54, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511809187.  Google Scholar

[23]

A. Kawamura, H. Thies and M. Ziegler, Average-case polynomial-time computability of Hamiltonian dynamics, in 43rd International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.  Google Scholar

[24]

K.-I. Ko, Complexity Theory of Real Functions. Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1991. doi: 10.1007/978-1-4684-6802-1.  Google Scholar

[25]

P. Koiran, The topological entropy of iterated piecewise affine maps is uncomputable, Discrete Math. Theor. Comput. Sci., 4 (2001), 351-356.   Google Scholar

[26]

P. Kůrka, On topological dynamics of Turing machines, Theoret. Comput. Sci., 174 (1997), 203-216.  doi: 10.1016/S0304-3975(96)00025-4.  Google Scholar

[27]

J. Milnor, Is entropy effectively computable?, Semantic Scholar, (2002). Google Scholar

[28]

M. Misiurewicz and W. Szlenk, Entropy of piecewise monotone mappings, Studia Math., 67 (1977), 45-63.  doi: 10.4064/sm-67-1-45-63.  Google Scholar

[29]

C. Moore, Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett., 64 (1990), 2354-2357.  doi: 10.1103/PhysRevLett.64.2354.  Google Scholar

[30]

S. Ruette, Chaos on the interval - a survey of relationship between the various kinds of chaos for continuous interval maps, preprint, arXiv: 1504.03001 Google Scholar

[31]

C. Spandl, Computing the topological entropy of shifts, MLQ Math. Log. Q., 53 (2007), 493-510.  doi: 10.1002/malq.200710014.  Google Scholar

[32]

G. Swiatek, Hyperbolicity is dense in the real quadratic family, preprint, arXiv: math/9207219. Google Scholar

[33]

X. Zheng and K. Weihrauch, The arithmetical hierarchy of real numbers, MLQ Math. Log. Q., 47 (2001), 51-65.  doi: 10.1002/1521-3870(200101)47:1<51::AID-MALQ51>3.0.CO;2-W.  Google Scholar

Figure 1.  Illustration of the definition of the sets $ \Delta_m $ and $ \Delta_{2m} $ for some $ m \ge 0 $
Figure 2.  Illustration of the propagation of the error symbol $ \# $ under the action of $ f $
Figure 3.  Illustration of the map $ g_h $ when $ s = 3/2 $
Figure 4.  Illustration of an example of map $ \tilde{g}_h $, when $ h_1 = h_2 = \log_2(3/2) $ and $ h_3 = 1 $
Figure 5.  Bifurcation Diagram: it plots the attractor of the map $ f_r $ as a function of the parameter $ r\in[3,4] $
[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]

Yun Zhao, Wen-Chiao Cheng, Chih-Chang Ho. Q-entropy for general topological dynamical systems. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2059-2075. doi: 10.3934/dcds.2019086

[3]

Xiaomin Zhou. Relative entropy dimension of topological dynamical systems. Discrete & Continuous Dynamical Systems - A, 2019, 39 (11) : 6631-6642. doi: 10.3934/dcds.2019288

[4]

Wen-Guei Hu, Song-Sun Lin. On spatial entropy of multi-dimensional symbolic dynamical systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (7) : 3705-3717. doi: 10.3934/dcds.2016.36.3705

[5]

João Ferreira Alves, Michal Málek. Zeta functions and topological entropy of periodic nonautonomous dynamical systems. Discrete & Continuous Dynamical Systems - A, 2013, 33 (2) : 465-482. doi: 10.3934/dcds.2013.33.465

[6]

José S. Cánovas. Topological sequence entropy of $\omega$–limit sets of interval maps. Discrete & Continuous Dynamical Systems - A, 2001, 7 (4) : 781-786. doi: 10.3934/dcds.2001.7.781

[7]

Stefano Galatolo. Global and local complexity in weakly chaotic dynamical systems. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1607-1624. doi: 10.3934/dcds.2003.9.1607

[8]

Nicoletta Del Buono, Cinzia Elia, Roberto Garrappa, Alessandro Pugliese. Preface: "Structural Dynamical Systems: Computational aspects". Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : i-i. doi: 10.3934/dcdsb.201807i

[9]

Alfredo Marzocchi, Sara Zandonella Necca. Attractors for dynamical systems in topological spaces. Discrete & Continuous Dynamical Systems - A, 2002, 8 (3) : 585-597. doi: 10.3934/dcds.2002.8.585

[10]

Jakub Šotola. Relationship between Li-Yorke chaos and positive topological sequence entropy in nonautonomous dynamical systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 5119-5128. doi: 10.3934/dcds.2018225

[11]

Jérôme Rousseau, Paulo Varandas, Yun Zhao. Entropy formulas for dynamical systems with mistakes. Discrete & Continuous Dynamical Systems - A, 2012, 32 (12) : 4391-4407. doi: 10.3934/dcds.2012.32.4391

[12]

Yujun Zhu. Preimage entropy for random dynamical systems. Discrete & Continuous Dynamical Systems - A, 2007, 18 (4) : 829-851. doi: 10.3934/dcds.2007.18.829

[13]

Steven M. Pederson. Non-turning Poincaré map and homoclinic tangencies in interval maps with non-constant topological entropy. Conference Publications, 2001, 2001 (Special) : 295-302. doi: 10.3934/proc.2001.2001.295

[14]

H. M. Hastings, S. Silberger, M. T. Weiss, Y. Wu. A twisted tensor product on symbolic dynamical systems and the Ashley's problem. Discrete & Continuous Dynamical Systems - A, 2003, 9 (3) : 549-558. doi: 10.3934/dcds.2003.9.549

[15]

Chao Ma, Baowei Wang, Jun Wu. Diophantine approximation of the orbits in topological dynamical systems. Discrete & Continuous Dynamical Systems - A, 2019, 39 (5) : 2455-2471. doi: 10.3934/dcds.2019104

[16]

Boris Hasselblatt, Zbigniew Nitecki, James Propp. Topological entropy for nonuniformly continuous maps. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 201-213. doi: 10.3934/dcds.2008.22.201

[17]

Dongkui Ma, Min Wu. Topological pressure and topological entropy of a semigroup of maps. Discrete & Continuous Dynamical Systems - A, 2011, 31 (2) : 545-556. doi: 10.3934/dcds.2011.31.545

[18]

David Burguet. Examples of $\mathcal{C}^r$ interval map with large symbolic extension entropy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (3) : 873-899. doi: 10.3934/dcds.2010.26.873

[19]

Peter Ashwin, Xin-Chu Fu. Symbolic analysis for some planar piecewise linear maps. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1533-1548. doi: 10.3934/dcds.2003.9.1533

[20]

Marta Štefánková. Inheriting of chaos in uniformly convergent nonautonomous dynamical systems on the interval. Discrete & Continuous Dynamical Systems - A, 2016, 36 (6) : 3435-3443. doi: 10.3934/dcds.2016.36.3435

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (80)
  • HTML views (86)
  • Cited by (1)

[Back to Top]