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

Silvére Gangloff; Alonso Herrera; Cristobal Rojas; Mathieu Sablik

doi:10.3934/dcds.2020180

Article Contents

2020, Volume 40, Issue 7: 4259-4286. Doi: 10.3934/dcds.2020180

This issue Previous Article Models of nonlinear acoustics viewed as approximations of the Kuznetsov equation Next Article On weak-strong uniqueness and singular limit for the compressible Primitive Equations

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

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

Abstract / Introduction Full Text(HTML) Figure(5) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 37B40, 03D78.

Citation:

Full Text(HTML)

Figure 1. Illustration of the definition of the sets $ \Delta_m $ and $ \Delta_{2m} $ for some $ m \ge 0 $

Download: Full-size image PowerPoint slide

Figure 2. Illustration of the propagation of the error symbol $ \# $ under the action of $ f $

Download: Full-size image PowerPoint slide

Figure 3. Illustration of the map $ g_h $ when $ s = 3/2 $

Download: Full-size image PowerPoint slide

Figure 4. Illustration of an example of map $ \tilde{g}_h $, when $ h_1 = h_2 = \log_2(3/2) $ and $ h_3 = 1 $

Download: Full-size image PowerPoint slide

Figure 5. Bifurcation Diagram: it plots the attractor of the map $ f_r $ as a function of the parameter $ r\in[3,4] $

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	R. L. Adler, A. 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. Binder, M. Braverman, C. 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. Burr, M. 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. Cubitt, D. 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. Galatolo, M. 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. Hurd, J. 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.