October 7, 2019
Pascal Vanier (LACL - UPEC)Les sous-shifts sont des coloriages de $\mathbb{Z}^d$ verifiant des contraintes locales. Très tôt l’étude de sous-shifts en dimension supérieure à 2 a vu deux notions apparaître naturellement : l’apériodicité et l’indécidabilité. Nous explorons ces deux notions dans ce manuscrit, la seconde par le prisme de différentes notions de complexité, puis nous introduisons un nouveau regard sur les sous-shifts par le biais d’analogies avec la théorie des groupes.
Les sous-shifts sans point périodique, dits apériodiques, ont fait leur apparition avec la construction de Berger prouvant l’indécidabilité de la pavabilité du plan avec le formalisme des tuiles de Wang. Les sous-shifts apériodiques
ont ensuite été l’ingrédient principal de la plupart des constructions. Dans ce document nous nous intéressons
à la notion duale qui consiste à contenir un point apériodique. Nous montrons que les sous-shifts contenant un
point apériodique en contiennent toujours avec une apériodicité régulière : dans des boules concentriques
dont le rayon ne dépend que de la période.
La complexité dans les sous-shifts peut prendre plusieurs formes. Nous illustrons ici les différents liens qui unissent certaines de ces notions de complexité : complexité de Kolmogorov, complexité des configurations via le spectre des degrés Turing, ainsi que complexité au sens du nombre de motifs.
Nous introduisons en fin de manuscrit des analogies avec la théorie des groupes qui nous permettent d’énoncer
des analogues aux théorèmes de Higman dans le cadre des sous-shifts.