Shift spaces on groups : computability and dynamics

Barbieri Lemp, Sebastián Andrés

HAL, NNT: 2017LYSEN021 / Harvested from HAL

Résumé

Les sous-décalages sont des ensembles de coloriages d'un groupe définis en excluant certains motifs, et munis d'une action de décalage. Ces objets apparaissent naturellement comme discrétisations de systèmes dynamiques : à partir d'une partition de l'espace, on associe à chaque point de ce-dernier la suite des partitions visitées sous l'action du système.Plusieurs résultats récents ont mis en évidence la riche interaction entre la dynamique des sous-décalages et leur propriétés algorithmiques. Un exemple remarquable est la classification des entropies des sous-décalages multidimensionnels de type fini comme l'ensemble des nombres récursivement énumérables à droite. Cette thèse s'intéresse aux sous-décalages avec une approche double : d'un côté on s'intéresse à leurs propriétés dynamiques et de l'autre on les étudie comme des modèles de calcul.Cette thèse contient plusieurs résultats : une condition combinatoire suffisante prouvant qu'un sous-décalage dans un groupe dénombrable est non-vide, un théorème de simulation qui réalise une action effective d'un groupe de type fini comme un facteur d'une sous-action d'un sous-décalage de type fini, une caractérisation de l'effectivité à l'aide de machines de Turing généralisées et l'indécidabilité du problème de torsion pour deux groupes, qui sont invariants de systèmes dynamiques.Comme corollaires de nos résultats, nous obtenons d'abord une preuve courte de l'existence de sous-décalages fortement apériodiques sur tout groupe dénombrable. Puis, dans le cas d'un produit semi-direct de la grille bidimensionnelle avec un groupe de type fini avec problème du mot décidable, nous montrons que le sous-décalage obtenu est de type fini.

Détail

Publié le : 2017-06-28
Classification:  Conjugacy invariants,  Group theory,  Simulation theorems,  Symbolic dynamics,  Dynamical systems,  Shift spaces,  Aperiodicity,  Computability,  Dynamique symbolique,  Systèmes dynamiques,  Sous-décalages,  Aperiodicité,  Calculabilité,  Théorèmes de simulation,  Théorie des groupes,  Invariants de conjugaison,  [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL],  [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS]