A characterization of the entropies of multidimensional shifts of finite type (Q974081)

To a finite alphabet \(\Sigma\) there is associated \(\Sigma^{Z^d}\) - the space of \(\Sigma\)-colorings of \(Z^d\) or the full shift on \(\Sigma\). A shift of finite type is a set of colorings defined by local rules. The paper is concerned with their topological entropy as a measure of asymptotic growth of the number of colorings of finite regions. It is proved that the entropy of any shift of finite type is right recursively enumerable. The main part of the paper deals with the proof of the following basic result. Theorem. For \(d\geq 2\) the class of entropies of \(d\)-dimensional shifts of finite type is the class of nonnegative right recursively enumerable numbers.