Liens transverses ENS de Lyon

Agenda de l'ENS de Lyon

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

Soutenance de thèse

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


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

Description générale
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.

Amphi B - Site Monod - ENS de Lyon