A Characterization of the Entropies of Multidimensional Shifts of Finite Type

Abstract

We show that the values of entropies of multidimensional shifts of finite type (SFTs) are characterized by a certain computation-theoretic property: a real number $h\ge 0$ is the entropy of such an SFT if and only if it is right recursively enumerable, i.e. there is a computable sequence of rational numbers converging to $h$ from above. The same characterization holds for the entropies of sofic shifts. On the other hand, the entropy of an irreducible SFT is computable.

27 pages, 2 figures

Cited by in corpus (17)

• On the zero-temperature limit of Gibbs states
• A notion of effectiveness for subshifts on finitely generated groups
• Representation and poly-time approximation for pressure of ${\mathbb{Z}}^2$ lattice models in the non-uniqueness region
• A generalization of the simulation theorem for semidirect products
• Mixing properties of tree-shifts
• Verification of mixing properties in two-dimensional shifts of finite type
• Weak colored local rules for planar tilings
• Markov partitions for toral ${\mathbb{Z}}^2$-rotations featuring Jeandel-Rao Wang shift and model sets
• Rauzy induction of polygon partitions and toral ${\mathbb{Z}}^2$-rotations
• Direct topological factorization for topological flows
• Subsystem entropies of shifts of finite type and sofic shifts on countable amenable groups
• A geometric simulation theorem on direct products of finitely generated groups
• Rohlin properties for $Z^d$-actions on the Cantor set
• Slopes of 3-dimensional Subshifts of Finite Type
• The expressiveness of quasiperiodic and minimal shifts of finite type
• Arithmetical Hierarchy of the Besicovitch-Stability of Noisy Tilings
• Characterisation of the Set of Ground States of Uniformly Chaotic Finite-Range Lattice Models