Multidimensional shifts of finite type and sofic shifts

Introduction In this chapter we discuss (multidimensional) shifts of finite type , or SFTs for short. These are the sets X(ℰ) ⊆ Σ Z d of d -dimensional configurations that arise by forbidding the occurrence of a finite list ℰ of finite patterns. This local, combinatorial and perhaps naive definition leads to surprisingly complex behaviour, and therein lies some of the interest in these objects. SFTs also arise independently in a variety of contexts, including language theory, statistical physics, dynamical systems theory and the theory of cellular automata. We shall touch upon some of these connections later on. The answer to the question ‘what do SFTs look like’ turns out to be profoundly different depending on whether one works in dimension one or higher. In dimension one, the configurations in an SFT X(ℰ) can be described constructively: there is a certain finite directed graph G , derived explicitly from ℰ, such that X(ℰ) is (isomorphic to) the set of bi-infinite vertex paths in G . Most of the elementary questions, and many of the hard ones, can then be answered by combinatorial and algebraic analysis of G and its adjacency matrix. For a brief account of these matters, see Section 9.2.5. In dimension d ≥ 2, which is our main focus here, things are entirely different. First and foremost, given ℰ, one cannot generally give a constructive description of the elements of X(ℰ). In fact, Berger showed in 1966 that it is impossible even to decide, given ℰ, whether X(ℰ) = ∅. Consequently, nearly any other property or quantity associated with X(ℰ) is undecidable or uncomputable. What this tells us is that, in general, we cannot hope to know what a particular SFT behaves like. But one can still hope to classify the types of behaviours that can occur in the class of SFTs, and, quite surprisingly, it has emerged in recent years that for many properties of SFTs such a classification exists. The development of this circle of ideas began with the characterisation of the possible rates of ‘word-growth’ (topological entropy) of SFTs, and was soon followed by a characterisation of the degrees of computability (in the sense of Medvedev and Muchnik) of SFTs, and of the languages that arise by restricting configurations of SFTs to lower-dimensional lattices.