TY - JOUR

T1 - Computability of topological entropy

T2 - From general systems to transformations on cantor sets and the interval

AU - Gangloff, Silvére

AU - Herrera, Alonso

AU - Rojas, Cristobal

AU - Sablik, Mathieu

N1 - Funding Information:
2010 Mathematics Subject Classification. 37B40, 03D78. Key words and phrases. Topological entropy, computable analysis, computational complexity, dynamical systems, interval maps, symbolic systems. 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”.

PY - 2020/7/1

Y1 - 2020/7/1

N2 - 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 Σ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 Σ2-computable numbers can already be realized within the class of surjective computable maps over {0, 1}N, but that this bound decreases to Π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}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 Σ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.

AB - 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 Σ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 Σ2-computable numbers can already be realized within the class of surjective computable maps over {0, 1}N, but that this bound decreases to Π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}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 Σ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.

KW - Computable analysis

KW - Computational complexity

KW - Dynamical systems

KW - Interval maps

KW - Symbolic systems

KW - Topological entropy

UR - http://www.scopus.com/inward/record.url?scp=85083524266&partnerID=8YFLogxK

U2 - 10.3934/dcds.2020180

DO - 10.3934/dcds.2020180

M3 - Article

AN - SCOPUS:85083524266

VL - 40

SP - 4259

EP - 4286

JO - Discrete and Continuous Dynamical Systems

JF - Discrete and Continuous Dynamical Systems

SN - 1078-0947

IS - 7

ER -