Simpson, Medvedev Degrees of two-Dimensional Subshifts of Finite Type, Ergodic Theory Dynam. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Schraudner, Entropies realizable by block gluing shifts of finite type, J. Mozes, Tilings, substitution systems and dynamical systems generated by them, J. Meyerovitch, Growth-type invariants for zd subshifts of finite type and arithmetical classes of real numbers, Invent. Vanier, Characterizations of periods of multidimensional shifts, Ergodic Theory Dynam. Vanier, Turing degrees of multidimensional SFT, Theoret. Koh Park, Topological entropy dimension and directional entropy dimension for z2-subshifts, Entropy 19 (2017), 46.Į. Definition 6.3.3 (Informal Definition) A tileset is substitutive if the set of tilings by is, up to a recoloring, a. We refer to other articles in this volume for details on subshifts. The term subshift comes from the symbolic dynamics school. Vanier, Turing spectra of minimal subshifts, in Computer Science-Theory and Applications, Springer, Cham, 2017, pp. Intuitively the substitutive subshift S looks like k (w) at the infinity. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Hedlund, Endormorphisms and automorphisms of the shift dynamical system, Math.

Sablik, A characterization of the entropy dimensions of minimal ℤ 3- SFTs, preprint, arXiv:1712.03182. Hellouin, Effect of quantified irreducibility on computability of subshifts entropy, Discrete Contin. Shen, Fixed-point tile sets and their applications, J. Romashchenko, On the expressive power of quasiperiodic SFT, in 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, 2017, pp. Ballier, Propriétés Structurelles, Combinatoires et Logiques des Pavages, PhD Thesis, Universite de Provence Aix-Marseille, Marseille, 2009.ī. Sablik, Multidimensional effective s-adic subshift are sofic, Unif. Sablik, Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Appl.

Subshift rt