Hierarchy and Expansiveness in Two-Dimensional Subshifts of Finite Type

Subshifts are sets of con���gurations over an in���nite grid de���ned by a set of forbidden patterns. In this thesis, we study two-dimensional subshifts of���nite type (2D SFTs), where the underlying grid is Z2 and the set of for-bidden patterns is ���nite. We are mainly interested in the interplay between the computational power of 2D SFTs and their geometry, examined through the concept of expansive subdynamics. 2D SFTs with expansive directions form an interesting and natural class of subshifts that lie between dimensions 1 and 2. An SFT that has only one non-expansive direction is called extremely expansive. We prove that in many aspects, extremely expansive 2D SFTs display the totality of behaviours of general 2D SFTs. For example, we construct an aperiodic extremely expansive 2D SFT and we prove that the emptiness problem is undecidable even when restricted to the class of extremely expansive 2D SFTs. We also prove that every Medvedev class contains an extremely expansive 2D SFT and we provide a characterization of the sets of directions that can be the set of non-expansive directions of a 2D SFT. Finally, we prove that for every computable sequence of 2D SFTs with an expansive direction, there exists a universal object that simulates all of the elements of the sequence. We use the so called hierarchical, self-simulating or ���xed-point method for constructing 2D SFTs which has been previously used by Ga��cs, Durand, Romashchenko and Shen.