Cette thèse est dédiée à l'étude des pavages : des ensembles de coloriages du plan discret respectant des contraintes locales données par un jeu de tuiles. Nous nous penchons en particulier sur les liens qui unissent les pavages et la calculabilité. Les pavages étant des ensembles effectivement clos particuliers, nous étudions dans un premier temps la structure des ensembles de degrés Turing des pavages, la comparant à celle des ensembles effectivement clos en général : pour tout ensemble effectivement clos il existe un pavage qui a les même degrés Turing à 0 près, le degré des ensembles récursifs. De plus les pavages ne contenant pas de membre récursif ont une structure particulière : ils contiennent toujours un cône de degrés Turing, un degré Turing et tous les degrés qui lui sont supérieurs. Dans un second temps, nous étudions les ensembles de périodes des pavages, pour diverses notions de périodicité, parvenant à des caractérisations à l'aide de classes de complexité ou de calculabilité pour chaque notion étudiée. Enfin nous nous intéressons à la difficulté calculatoire des problèmes de la factorisation et de la conjugaison, des notions de simulation et d'équivalence adaptées aux spécificités des pavages. / This thesis is dedicated to the study of subshifts of finite type (SFTs) : sets of colorings of the discrete plane which respect some local constraints given by a set of forbidden patterns. We study the links between SFTs and computation. SFTs being specific effectively closed classes, we fist study their Turing degree structure, comparing it to the one of effectively closed classes in general: for any effectively closed class, there exist an SFT having the same Turing degrees except maybe 0, the degree of recursive sets. Furthermore, SFTs containing no recursive member have a particular structure: they always contain a cone of Turing degrees, ie. a Turing degree and all degrees above it. We then study the sets of periods of SFTs, for different notions of periodicity, reaching characterizations by means of computational complexity classes or computability classes for each notion introduced. Finally we look at the computable hardness of the factorization and conjugacy problems, the right notions of simulation and equivalence for SFTs.

Les automates cellulaires sont à la fois un modèle de calcul parallèle, un système complexe et un système dynamique. Ils fonctionnent de manière synchrone et en temps discret, leur particularité est que les fonctions qu'ils définissent sont issues de l'application simultanée, en tout point de l'espace, d'une règle d'évolution locale. L'ensemble limite est un objet classique des systèmes dynamiques, c'est l'ensemble des états que le système peut atteindre arbitrairement tard. Il a été très étudié dans le cadre des automates cellulaires, et les résultats sont nombreux. Parmi ces résultats, un théorème de Rice démontré par Jarkko Kari dit que toute propriété des ensembles limites est indécidable. Dans ce mémoire, on ne s'intéresse plus à l'ensemble limite traditionnel, mais à une variante pour laquelle on utilise une mesure sur l'espace des entrées, sélectionnant ainsi les comportements susceptibles d'apparaître arbitrairement tard et souvent. Ce nouvel ensemble, que l'on nomme ensemble mu-limite, a été introduit en 2000 par Petr Kurka et Alejandro Maass. La plupart des résultats sur les ensembles limites ne se transposent pas naturellement. On étudie la famille des ensembles mu-limites d'automates cellulaires. On montre que sous certaines contraintes sur la dynamique, l'ensemble mu-limite peut être entièrement décrit. On classe ainsi les automates en fonction de ces contraintes. Dans le cas général, on montre l'existence d'automates cellulaires ayant comme ensembles mu-limites un grand nombre d'ensembles complexes. On finit par montrer un théorème de Rice pour les ensembles mu-limites d'automates cellulaires: tout propriété non triviale de ces ensembles est indécidable. / Cellular automata are simultaneously a model of parallel computation, a complex system and a dynamical system. They are synchronous and time is discrete. The functions defined by their application is the result of the synchronous application of the same local rule everywhere. The limit set is a classical tool of dynamical systems theory, it is the set of states the system can reach arbitrarily late. It has been studied often in the particular case of cellular automata and there are numerous results. Amongst them, a Rice's theorem proved by Jarkko Kari states that any non-trivial property of limit sets of cellular automata is undecidable. In this thesis, we do not consider the classical limit set, as we add a measure on the space of states of the system. Thus, we get a set which contains behaviors that appear arbitrarily far and often. This set is named mu-limit set and was introduced in 2000 by Petr Kurka and Alejandro Maass. Most of the results on limit sets cannot be directly adapted for mu-limit sets. We study the family of all mu-limit sets of cellular automata. We show that under some constraints on the dynamics, the mu-limit set can be entirely described. We then produce a classification of cellular automata according to these constraints. In the general case, we prove the existence of cellular automata whose mu-limit sets are among a large set of complex sets. We finally prove Rice's theorem for mu-limit sets: any non-trivial property is undecidable.