
-
Previous Article
Entire solutions and traveling wave solutions of the Allen-Cahn-Nagumo equation
- DCDS Home
- This Issue
-
Next Article
Binary differential equations with symmetries
Effect of quantified irreducibility on the computability of subshift entropy
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 |
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.
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. |
[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. |
[3] |
K. Engel,
On the Fibonacci number of an m×n lattice, Fibonacci Quart, 28 (1990), 72-78.
|
[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. |
[6] |
P. Hertling and C. Spandl,
Shifts with decidable language and non-computable entropy, Discrete Mathematics and Theoretical Computer Science, 10 (2008), 75-93.
|
[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. |
[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. |
[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. |
[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. |
[11] |
P. Koiran,
The topological entropy of iterated piecewise affine maps is uncomputable, Theoretical Computer Science, 4 (2001), 351-356.
|
[12] |
E. H. Lieb, Residual entropy of square ice, Physical Review, 162 (1967), 162.
doi: 10.1103/PhysRev.162.162. |
[13] |
D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge university press, 1995.
doi: 10.1017/CBO9780511626302.![]() ![]() |
[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. |
[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. |
[17] |
M. Misiurewicz,
On non-continuity of topological entropy, Bull. Ac. Pol. Sci. Ser. Sci. Math. Astr. Phys., 19 (1971), 319-320.
|
[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. |
[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. |
[20] |
J. G. Simonsen,
On the computability of the topological entropy of subshifts, Discrete Mathematics and Theoretical Computer Science, 8 (2006), 83-95.
|
[21] |
C. Spandl,
Computing the topological entropy of shifts, Mathematical Logic Quarterly, 53 (2007), 493-510.
doi: 10.1002/malq.200710014. |
[22] |
B. Stanley,
Bounded density shifts, Ergodic Theory and Dynamical Systems, 33 (2013), 1891-1928.
doi: 10.1017/etds.2013.38. |
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. |
[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. |
[3] |
K. Engel,
On the Fibonacci number of an m×n lattice, Fibonacci Quart, 28 (1990), 72-78.
|
[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. |
[6] |
P. Hertling and C. Spandl,
Shifts with decidable language and non-computable entropy, Discrete Mathematics and Theoretical Computer Science, 10 (2008), 75-93.
|
[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. |
[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. |
[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. |
[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. |
[11] |
P. Koiran,
The topological entropy of iterated piecewise affine maps is uncomputable, Theoretical Computer Science, 4 (2001), 351-356.
|
[12] |
E. H. Lieb, Residual entropy of square ice, Physical Review, 162 (1967), 162.
doi: 10.1103/PhysRev.162.162. |
[13] |
D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge university press, 1995.
doi: 10.1017/CBO9780511626302.![]() ![]() |
[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. |
[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. |
[17] |
M. Misiurewicz,
On non-continuity of topological entropy, Bull. Ac. Pol. Sci. Ser. Sci. Math. Astr. Phys., 19 (1971), 319-320.
|
[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. |
[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. |
[20] |
J. G. Simonsen,
On the computability of the topological entropy of subshifts, Discrete Mathematics and Theoretical Computer Science, 8 (2006), 83-95.
|
[21] |
C. Spandl,
Computing the topological entropy of shifts, Mathematical Logic Quarterly, 53 (2007), 493-510.
doi: 10.1002/malq.200710014. |
[22] |
B. Stanley,
Bounded density shifts, Ergodic Theory and Dynamical Systems, 33 (2013), 1891-1928.
doi: 10.1017/etds.2013.38. |




Subshift class | Mixing properties | |||
None | Weak | Strong | Very strong | |
SFT | ? | computable |
computable [8] | |
all |
? | ? | partial char. [19] | |
Decidable | computable |
computable [21] | ||
all |
all |
? | ? |
Subshift class | Mixing properties | |||
None | Weak | Strong | Very strong | |
SFT | ? | computable |
computable [8] | |
all |
? | ? | partial char. [19] | |
Decidable | computable |
computable [21] | ||
all |
all |
? | ? |
[1] |
Scott Schmieding, Rodrigo Treviño. Random substitution tilings and deviation phenomena. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3869-3902. doi: 10.3934/dcds.2021020 |
[2] |
Bing Gao, Rui Gao. On fair entropy of the tent family. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3797-3816. doi: 10.3934/dcds.2021017 |
[3] |
Elena Bonetti, Pierluigi Colli, Gianni Gilardi. Singular limit of an integrodifferential system related to the entropy balance. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1935-1953. doi: 10.3934/dcdsb.2014.19.1935 |
[4] |
A. Kochergin. Well-approximable angles and mixing for flows on T^2 with nonsingular fixed points. Electronic Research Announcements, 2004, 10: 113-121. |
[5] |
Fei Liu, Xiaokai Liu, Fang Wang. On the mixing and Bernoulli properties for geodesic flows on rank 1 manifolds without focal points. Discrete & Continuous Dynamical Systems, 2021 doi: 10.3934/dcds.2021057 |
[6] |
Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225 |
[7] |
Simone Calogero, Juan Calvo, Óscar Sánchez, Juan Soler. Dispersive behavior in galactic dynamics. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 1-16. doi: 10.3934/dcdsb.2010.14.1 |
[8] |
Patrick Henning, Anders M. N. Niklasson. Shadow Lagrangian dynamics for superfluidity. Kinetic & Related Models, 2021, 14 (2) : 303-321. doi: 10.3934/krm.2021006 |
[9] |
Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83 |
[10] |
Marcel Braukhoff, Ansgar Jüngel. Entropy-dissipating finite-difference schemes for nonlinear fourth-order parabolic equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3335-3355. doi: 10.3934/dcdsb.2020234 |
[11] |
Hsin-Lun Li. Mixed Hegselmann-Krause dynamics. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021084 |
[12] |
Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53 |
[13] |
Yu Jin, Xiao-Qiang Zhao. The spatial dynamics of a Zebra mussel model in river environments. Discrete & Continuous Dynamical Systems - B, 2021, 26 (4) : 1991-2010. doi: 10.3934/dcdsb.2020362 |
[14] |
Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3295-3317. doi: 10.3934/dcds.2020406 |
[15] |
Mirelson M. Freitas, Anderson J. A. Ramos, Manoel J. Dos Santos, Jamille L.L. Almeida. Dynamics of piezoelectric beams with magnetic effects and delay term. Evolution Equations & Control Theory, 2021 doi: 10.3934/eect.2021015 |
[16] |
Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183 |
[17] |
Guirong Jiang, Qishao Lu. The dynamics of a Prey-Predator model with impulsive state feedback control. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1301-1320. doi: 10.3934/dcdsb.2006.6.1301 |
[18] |
Mingxin Wang, Qianying Zhang. Dynamics for the diffusive Leslie-Gower model with double free boundaries. Discrete & Continuous Dynamical Systems, 2018, 38 (5) : 2591-2607. doi: 10.3934/dcds.2018109 |
[19] |
Yuyue Zhang, Jicai Huang, Qihua Huang. The impact of toxins on competition dynamics of three species in a polluted aquatic environment. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3043-3068. doi: 10.3934/dcdsb.2020219 |
[20] |
Yongjian Liu, Qiujian Huang, Zhouchao Wei. Dynamics at infinity and Jacobi stability of trajectories for the Yang-Chen system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3357-3380. doi: 10.3934/dcdsb.2020235 |
2019 Impact Factor: 1.338
Tools
Metrics
Other articles
by authors
[Back to Top]