This thesis is devoted to the study of subshifts, and in particular their computational properties. A subshift is defined by a finite set of symbols, a set of rules specifying authorized and forbidden arrangements of these symbols, and an ambient space that we try to tile: a valid configuration is then an arrangement of these symbols, covering the entire space and respecting all the rules. A subshift is then defined as the set of all the valid configurations. In the simplest case, the rules are adjacency rules, which prevent some symbols from being placed next to one another. However, even in this restricted setting, tilings of \(\mathbb{Z}^{d}\) for \(d > 1\) can be surprinsingly complicated, in several ways studied in this thesis.

The thesis is divided in three independent chapters, with a preliminary chapter introducing all the relevant background knowledge for the various objects being considered. In a first chapter, we study the extender entropy of \(\mathbb{Z}^{d}\) subshifts, a real number which quantifies for any subshift the number of patterns that can freely be exchanged in all the valid configurations. We show that the possible values of extender entropies are fully characterized by computability restrictions, more precisely, they correspond exactly to levels in the arithmetical hierarchy of real numbers, the precise level depending on the specific class of subshifts being considered. In a second chapter, we study the Projective Fundamental Group of \(\mathbb{Z}^{2}\)-subshifts, a group which aims at classifying the various kinds of obstructions encountered when trying to extend a partial configuration to a complete, valid configuration of the subshift. We show that even subshifts of finite type can have as fundamental group any finitely presented group. Finally, we study in a third chapter a kind of substitutive subshift defined on graphs. We propose a definition of substitutive graph, as well as substitutive graph subshift, and show that an important class of these subshifts can be obtained using only finitely many local rules. This partially generalizes a classical result from Mozes, in a more combinatorial but less geometrical setting.