A characterization of the entropies of multidimensional shifts of finite type


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\geq0$ 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 strongly irreducible SFTs is computable.


Michael Hochman

Department of Mathematics
Princeton University
Fine Hall - Washington Rd.
Princeton, NJ
United States
School of Mathematics
Institute for Advanced Study
Einstein Dr.
Princeton, NJ 08540
United States

Tom Meyerovitch

School of Mathematical Sciences
Tel Aviv University
Ramat Aviv
Tel Aviv 69978