A Characterization of the Entropies of Multidimensional Shifts of Finite Type

By Michael Hochman, Tom Meyerovitch. 2007

203 citations recorded by the source corpus.

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\geq 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.

Subfields: Computational Theory and Mathematics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/9845041b729771446f73a5ff1b7df2ff783059e3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Ronnie Pavlov
2. Michael Schraudner

In Mathematical Physics

1. Ronnie Pavlov
2. Michael Schraudner

Citations in the corpus

• Entropies realizable by block gluing ℤd shifts of finite type (2015, methodology): “It was already shown in [9] that in the presence of the strongest uniform mixing property, strong irreducibility, the entropies of Z SFTs must satisfy the strictly stronger recursion-theoretic condition of computability.”