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 and Continuous Dynamical Systems, 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.

[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.

[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.

[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.

[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.

[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.

[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.

[8]

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

[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.

[10] R. L. Devaney, An Introduction to Chaotic Dynamical Systems, Westview Press, Boulder, CO, 2003. 
[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.

[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.

[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.

[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.

[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.

[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.

[17]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[25]

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

[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.

[27]

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

[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.

[29]

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

[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

[31]

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

[32]

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

[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.

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.

[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.

[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.

[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.

[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.

[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.

[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.

[8]

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

[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.

[10] R. L. Devaney, An Introduction to Chaotic Dynamical Systems, Westview Press, Boulder, CO, 2003. 
[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.

[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.

[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.

[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.

[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.

[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.

[17]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[25]

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

[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.

[27]

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

[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.

[29]

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

[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

[31]

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

[32]

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

[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.

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 and Continuous Dynamical Systems - B, 2004, 4 (4) : 935-960. doi: 10.3934/dcdsb.2004.4.935

[2]

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

[3]

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

[4]

Wen-Guei Hu, Song-Sun Lin. On spatial entropy of multi-dimensional symbolic dynamical systems. Discrete and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 2003, 9 (6) : 1607-1624. doi: 10.3934/dcds.2003.9.1607

[8]

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

[9]

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

[10]

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

[11]

Khosro Sayevand, Valeyollah Moradi. A robust computational framework for analyzing fractional dynamical systems. Discrete and Continuous Dynamical Systems - S, 2021, 14 (10) : 3763-3783. doi: 10.3934/dcdss.2021022

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2020 Impact Factor: 1.392

Metrics

  • PDF downloads (283)
  • HTML views (95)
  • Cited by (2)

[Back to Top]