Accès direct au contenu


logo du site ENS

Logo du site Ens Lyon

30 ans de l'ENS de Lyon

Accueil  >  ENS de Lyon > Recherche > Soutenances de thèses > Thèses en sc. exactes et exp.


Shift spaces on groups : computability and dynamics - Calculabilité et dynamique des sous-décalages sur des groupes

Soutenance de thèse
Soutenance de thèse de M. Sebastian Andres BARBIERI LEMP du LIP sous la direction de M Stephan THOMASSE
28 juin 2017

Lieu(x) :

Site Monod - 46 allée d'Italie
Amphi B - Site Monod - ENS de Lyon
Shift spaces are sets of colorings of a group which avoid a set of forbidden patterns and are endowed with a shift action. These spaces appear naturally as discrete versions of dynamical systems: they are obtained by partitioning the phase space and mapping each element into the sequence of partitions visited by its orbit.

Several breakthroughs in this domain have pointed out the intricate relationship between dynamics of shift spaces and their computability properties. One remarkable example is the classification of the entropies of multidimensional subshifts of finite type as the set of right recursively enumerable numbers. This work explores shift spaces with a dual approach: on the one hand we are interested in their dynamical properties and on the other hand we study these objects as computational models.

Four salient results have been obtained as a result of this approach: (1) a combinatorial condition ensuring non-emptiness of subshifts on arbitrary countable groups; (2) a simulation theorem which realizes effective actions of finitely generated groups as factors of a subaction of a subshift of finite type; (3) a characterization of effectiveness with oracles using generalized Turing machines and (4) the undecidability of the torsion problem for two group invariants of shift spaces.

As byproducts of these results we obtain a simple proof of the existence of strongly aperiodic subshifts in countable groups. Furthermore, we realize them as subshifts of finite type in the case of a semidirect product of a d-dimensional integer lattice with a finitely generated group with decidable word problem where d>1.

Retour au haut de la page

Pôle Recherche
Mise à jour le 8 juin 2017
Ens de Lyon
15 parvis René Descartes - BP 7000 69342 Lyon Cedex 07 - FRANCE
Tél. : Site René Descartes (siège) : +33 (0) 4 37 37 60 00 / Site Jacques Monod : +33 (0) 4 72 72 80 00