Effect of quantified irreducibility on the computability of subshift entropy

Silvère Gangloff; Benjamin Hellouin de Menibus

doi:10.3934/dcds.2019083

Article Contents

2019, Volume 39, Issue 4: 1975-2000. Doi: 10.3934/dcds.2019083

This issue Previous Article Binary differential equations with symmetries Next Article Entire solutions and traveling wave solutions of the Allen-Cahn-Nagumo equation

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: January 31, 2018

Revised: July 31, 2018

Published: January 2019

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

Abstract Full Text(HTML) Figure(4) / Table(1) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 37B50, 37B40; Secondary: 37B10, 68Q17.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

Figure 2. Illustration of Definition 3.12

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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

Download: Full-size image 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
Subshift class	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$	?	?

| Show Table

DownLoad: CSV

Related Papers

Cited by

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