American Institute of Mathematical Sciences

Advanced
April  2019, 39(4): 1975-2000. doi: 10.3934/dcds.2019083

Effect of quantified irreducibility on the computability of subshift entropy

Silvère Gangloff 1, and  Benjamin Hellouin de Menibus 2,

1. 

Institut de Mathématiques de Toulouse, Université Paul Sabatier Toulouse 3,118 route de Narbonne, Toulouse, France
2. 

Laboratoire de Recherche en Informatique, Université Paris-Sud - CNRS - CentraleSupelec, Université Paris-Saclay, Btiment 650 Ada Lovelace, rue Noetzlin, Gif-sur-Yvette, France

Received  February 2018 Revised  August 2018 Published  January 2019

Fund Project: The second author was supported by Basal PFB-03 CMM, Universidad de Chile, and did this work in part at in part in the Departamento de Matématicas, Universidad Andrés Bello, Republica 220, Santiago, Chile and Centro de Modelamiento Matematico, Beauchef 851, Santiago, Chile

We study the algorithmic computability of topological entropy of subshifts subjected to a quantified version of a strong condition of mixing, called irreducibility. For subshifts of finite type, it is known that this problem goes from uncomputable to computable as the rate of irreducibility decreases. Furthermore, the set of possible values for the entropy goes from all right-recursively computable numbers to some subset of the computable numbers. However, the exact nature of the transition is not understood.

In this text, we characterize a computability threshold for subshifts with decidable language (in any dimension), expressed as a summability condition on the rate function. This class includes subshifts of finite type under the threshold, and offers more flexibility for the constructions involved in the proof of uncomputability above the threshold. These constructions involve bounded density subshifts that control the density of particular symbols in all subwords.

Keywords: Entropy, tilings, symbolic dynamics, subshift, computability, mixing, irreducilibity.
Mathematics Subject Classification: Primary: 37B50, 37B40; Secondary: 37B10, 68Q17.
Citation: Silvère Gangloff, Benjamin Hellouin de Menibus. Effect of quantified irreducibility on the computability of subshift entropy. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 1975-2000. doi: 10.3934/dcds.2019083
References:
[1]

M. D'amico, G. Manzini and L. Margara, On computing the entropy of cellular automata, Theoretical Computer Science, 290 (2003), 1629-1646.  doi: 10.1016/S0304-3975(02)00071-3.  Google Scholar

[2]

J.-C. Delvenne and V. D. Blondel, Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines, Theoretical Computer Science, 319 (2004), 127-143.  doi: 10.1016/j.tcs.2004.02.018.  Google Scholar

[3]

K. Engel, On the Fibonacci number of an m×n lattice, Fibonacci Quart, 28 (1990), 72-78.   Google Scholar

[4]

S. Gangloff and M. Sablik, Quantified block gluing: aperiodicity and entropy of multidimensional SFT, Preprint, https://arXiv.org/abs/1706.01627, 2017. Google Scholar

[5]

P. Guillon and C. Zinoviadis, Densities and entropies in cellular automata, In Conference on Computability in Europe, Springer, 7318 (2012), 253–263. doi: 10.1007/978-3-642-30870-3_26.  Google Scholar

[6]

P. Hertling and C. Spandl, Shifts with decidable language and non-computable entropy, Discrete Mathematics and Theoretical Computer Science, 10 (2008), 75-93.   Google Scholar

[7]

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

[8]

M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Annals of Mathematics, 171 (2010), 2011-2038.  doi: 10.4007/annals.2010.171.2011.  Google Scholar

[9]

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

[10]

E. Jeandel, Computability of the entropy of one-tape Turing machines, STACS-Symposium on Theoretical Aspects of Computer Science, 25 (2014), 421-432.  doi: 10.4230/LIPIcs.STACS.2014.421.  Google Scholar

[11]

P. Koiran, The topological entropy of iterated piecewise affine maps is uncomputable, Theoretical Computer Science, 4 (2001), 351-356.   Google Scholar

[12]

E. H. Lieb, Residual entropy of square ice, Physical Review, 162 (1967), 162. doi: 10.1103/PhysRev.162.162.  Google Scholar

[13] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge university press, 1995.  doi: 10.1017/CBO9780511626302.  Google Scholar
[14]

D. A. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory and Dynamical Systems, 4 (1984), 283-300.  doi: 10.1017/S0143385700002443.  Google Scholar

[15]

J. Milnor, Is the entropy effectively computable?, Unpublished note, http://www.math.stonybrook.edu/~jack/comp-ent.pdf. Google Scholar

[16]

J. Milnor and C. Tresser, On entropy and monotonicity for real cubic maps, Communications in Mathematical Physics, 209 (2000), 123-178.  doi: 10.1007/s002200050018.  Google Scholar

[17]

M. Misiurewicz, On non-continuity of topological entropy, Bull. Ac. Pol. Sci. Ser. Sci. Math. Astr. Phys., 19 (1971), 319-320.   Google Scholar

[18]

R. Pavlov et al., Approximating the hard square entropy constant with probabilistic methods, The Annals of Probability, 40 (2012), 2362-2399. doi: 10.1214/11-AOP681.  Google Scholar

[19]

R. Pavlov and M. Schraudner, Entropies realizable by block gluing $ \mathbb Z ^d$-subshifts of finite type, Journal d'Analyse Mathématique, 126 (2015), 113-174.  doi: 10.1007/s11854-015-0014-4.  Google Scholar

[20]

J. G. Simonsen, On the computability of the topological entropy of subshifts, Discrete Mathematics and Theoretical Computer Science, 8 (2006), 83-95.   Google Scholar

[21]

C. Spandl, Computing the topological entropy of shifts, Mathematical Logic Quarterly, 53 (2007), 493-510.  doi: 10.1002/malq.200710014.  Google Scholar

[22]

B. Stanley, Bounded density shifts, Ergodic Theory and Dynamical Systems, 33 (2013), 1891-1928.  doi: 10.1017/etds.2013.38.  Google Scholar

show all references

References:
[1]

M. D'amico, G. Manzini and L. Margara, On computing the entropy of cellular automata, Theoretical Computer Science, 290 (2003), 1629-1646.  doi: 10.1016/S0304-3975(02)00071-3.  Google Scholar

[2]

J.-C. Delvenne and V. D. Blondel, Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines, Theoretical Computer Science, 319 (2004), 127-143.  doi: 10.1016/j.tcs.2004.02.018.  Google Scholar

[3]

K. Engel, On the Fibonacci number of an m×n lattice, Fibonacci Quart, 28 (1990), 72-78.   Google Scholar

[4]

S. Gangloff and M. Sablik, Quantified block gluing: aperiodicity and entropy of multidimensional SFT, Preprint, https://arXiv.org/abs/1706.01627, 2017. Google Scholar

[5]

P. Guillon and C. Zinoviadis, Densities and entropies in cellular automata, In Conference on Computability in Europe, Springer, 7318 (2012), 253–263. doi: 10.1007/978-3-642-30870-3_26.  Google Scholar

[6]

P. Hertling and C. Spandl, Shifts with decidable language and non-computable entropy, Discrete Mathematics and Theoretical Computer Science, 10 (2008), 75-93.   Google Scholar

[7]

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

[8]

M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Annals of Mathematics, 171 (2010), 2011-2038.  doi: 10.4007/annals.2010.171.2011.  Google Scholar

[9]

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

[10]

E. Jeandel, Computability of the entropy of one-tape Turing machines, STACS-Symposium on Theoretical Aspects of Computer Science, 25 (2014), 421-432.  doi: 10.4230/LIPIcs.STACS.2014.421.  Google Scholar

[11]

P. Koiran, The topological entropy of iterated piecewise affine maps is uncomputable, Theoretical Computer Science, 4 (2001), 351-356.   Google Scholar

[12]

E. H. Lieb, Residual entropy of square ice, Physical Review, 162 (1967), 162. doi: 10.1103/PhysRev.162.162.  Google Scholar

[13] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge university press, 1995.  doi: 10.1017/CBO9780511626302.  Google Scholar
[14]

D. A. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory and Dynamical Systems, 4 (1984), 283-300.  doi: 10.1017/S0143385700002443.  Google Scholar

[15]

J. Milnor, Is the entropy effectively computable?, Unpublished note, http://www.math.stonybrook.edu/~jack/comp-ent.pdf. Google Scholar

[16]

J. Milnor and C. Tresser, On entropy and monotonicity for real cubic maps, Communications in Mathematical Physics, 209 (2000), 123-178.  doi: 10.1007/s002200050018.  Google Scholar

[17]

M. Misiurewicz, On non-continuity of topological entropy, Bull. Ac. Pol. Sci. Ser. Sci. Math. Astr. Phys., 19 (1971), 319-320.   Google Scholar

[18]

R. Pavlov et al., Approximating the hard square entropy constant with probabilistic methods, The Annals of Probability, 40 (2012), 2362-2399. doi: 10.1214/11-AOP681.  Google Scholar

[19]

R. Pavlov and M. Schraudner, Entropies realizable by block gluing $ \mathbb Z ^d$-subshifts of finite type, Journal d'Analyse Mathématique, 126 (2015), 113-174.  doi: 10.1007/s11854-015-0014-4.  Google Scholar

[20]

J. G. Simonsen, On the computability of the topological entropy of subshifts, Discrete Mathematics and Theoretical Computer Science, 8 (2006), 83-95.   Google Scholar

[21]

C. Spandl, Computing the topological entropy of shifts, Mathematical Logic Quarterly, 53 (2007), 493-510.  doi: 10.1002/malq.200710014.  Google Scholar

[22]

B. Stanley, Bounded density shifts, Ergodic Theory and Dynamical Systems, 33 (2013), 1891-1928.  doi: 10.1017/etds.2013.38.  Google Scholar

Figure 1.  Every pattern $v$ on $D_m$ appearing in some locally admissible pattern of $ \mathcal A ^{C_{N_0}}$ appears jointly with $u$ in some other locally admissible pattern
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Illustration of Definition 3.12
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Illustration of the definition of the function $ {\delta}_N $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Illustration of the definition of the algorithm. The sequence is already defined up to $ F^{n+1}(1) $. The number $ m^{*}_n $ is the smallest one such that the mixing condition is verified
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  (First line) Computational difficulty of computing the entropy; (Second line) Set of possible entropies. "Weak" and "Strong" mixing stand for irreducibility rates above or below the threshold, respectively; "Very strong" stands for constant irreducibility rates, or similar properties. "$ \Pi_1 $-comp." means that the problem is $ \Pi_1 $-computable, but not computable; "$ \Pi_1 $ reals" stands for the set of $ \Pi_1 $-computable reals; $ \dagger $ symbols indicate the contribution of the present article
Subshift class Mixing properties
None Weak Strong Very strong
SFT $\Pi_1$-comp. [8] ? computable $\dagger$ computable [8]
$d\geq 2$ all $\Pi_1$ reals [8] ? ? partial char. [19]
Decidable $\Pi_1$-comp. [20] $\Pi_1$-comp. $\dagger$ computable $\dagger$ computable [21]
$d\geq 1$ all $\Pi_1$ reals [6] all $\Pi_1$ reals $\dagger$ ? ?
Table Options

Download as excel

Subshift class Mixing properties
None Weak Strong Very strong
SFT $\Pi_1$-comp. [8] ? computable $\dagger$ computable [8]
$d\geq 2$ all $\Pi_1$ reals [8] ? ? partial char. [19]
Decidable $\Pi_1$-comp. [20] $\Pi_1$-comp. $\dagger$ computable $\dagger$ computable [21]
$d\geq 1$ all $\Pi_1$ reals [6] all $\Pi_1$ reals $\dagger$ ? ?
[1]

A. Crannell. A chaotic, non-mixing subshift. Conference Publications, 1998, 1998 (Special) : 195-202. doi: 10.3934/proc.1998.1998.195
[2]

Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487
[3]

Stefano Galatolo, Mathieu Hoyrup, Cristóbal Rojas. Dynamics and abstract computability: Computing invariant measures. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 193-212. doi: 10.3934/dcds.2011.29.193
[4]

Steven T. Piantadosi. Symbolic dynamics on free groups. Discrete & Continuous Dynamical Systems - A, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725
[5]

François Blanchard, Wen Huang. Entropy sets, weakly mixing sets and entropy capacity. Discrete & Continuous Dynamical Systems - A, 2008, 20 (2) : 275-311. doi: 10.3934/dcds.2008.20.275
[6]

Jim Wiseman. Symbolic dynamics from signed matrices. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 621-638. doi: 10.3934/dcds.2004.11.621
[7]

George Osipenko, Stephen Campbell. Applied symbolic dynamics: attractors and filtrations. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 43-60. doi: 10.3934/dcds.1999.5.43
[8]

Michael Hochman. A note on universality in multidimensional symbolic dynamics. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 301-314. doi: 10.3934/dcdss.2009.2.301
[9]

Piotr Oprocha, Paweł Potorski. Topological mixing, knot points and bounds of topological entropy. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3547-3564. doi: 10.3934/dcdsb.2015.20.3547
[10]

Jose S. Cánovas, Tönu Puu, Manuel Ruiz Marín. Detecting chaos in a duopoly model via symbolic dynamics. Discrete & Continuous Dynamical Systems - B, 2010, 13 (2) : 269-278. doi: 10.3934/dcdsb.2010.13.269
[11]

Nicola Soave, Susanna Terracini. Symbolic dynamics for the $N$-centre problem at negative energies. Discrete & Continuous Dynamical Systems - A, 2012, 32 (9) : 3245-3301. doi: 10.3934/dcds.2012.32.3245
[12]

Dieter Mayer, Fredrik Strömberg. Symbolic dynamics for the geodesic flow on Hecke surfaces. Journal of Modern Dynamics, 2008, 2 (4) : 581-627. doi: 10.3934/jmd.2008.2.581
[13]

Frédéric Naud. Birkhoff cones, symbolic dynamics and spectrum of transfer operators. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 581-598. doi: 10.3934/dcds.2004.11.581
[14]

David Ralston. Heaviness in symbolic dynamics: Substitution and Sturmian systems. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 287-300. doi: 10.3934/dcdss.2009.2.287
[15]

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
[16]

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
[17]

Mike Boyle, Tomasz Downarowicz. Symbolic extension entropy: $c^r$ examples, products and flows. Discrete & Continuous Dynamical Systems - A, 2006, 16 (2) : 329-341. doi: 10.3934/dcds.2006.16.329
[18]

Arnaud Goullet, Ian Glasgow, Nadine Aubry. Dynamics of microfluidic mixing using time pulsing. Conference Publications, 2005, 2005 (Special) : 327-336. doi: 10.3934/proc.2005.2005.327
[19]

Anke D. Pohl. Symbolic dynamics for the geodesic flow on two-dimensional hyperbolic good orbifolds. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 2173-2241. doi: 10.3934/dcds.2014.34.2173
[20]

Nicola Soave, Susanna Terracini. Addendum to: Symbolic dynamics for the $N$-centre problem at negative energies. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3825-3829. doi: 10.3934/dcds.2013.33.3825

2018 Impact Factor: 1.143

Tools

Metrics

  • PDF downloads (34)
  • HTML views (44)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences