Date(s) : 28/06/2018 iCal
14 h 00 min - 16 h 00 min
Soutenance de thèse
–
Complexité algorithmique des invariants de type croissance des sous-décalages de type fini sous contrainte dynamique
Les sous-décalages multidimensionnels (SFT) sont des ensembles de colorations d’une grille régulière innie (Zd,d ≥ 2) dénis par lois locales. Ces objets sont impliqués dans plusieurs domaines des mathématiques et en particulier la physique statistique. Un problème important dans ce cadre est de trouver une formule pour l’entropie. Excepté pour quelques modèles, une telle formule n’est pas connue. De plus, il a été démontré relativement récemment qu’il n’existe pas de méthode pour calculer (algorithmiquement) l’entropie de ces systèmes. Par conséquent, une approche naturelle au problème est de chercher une sous-classe (maximale) sur laquelle il existe un algorithme permettant de calculer uniformément l’entropie.
Dans ce texte, on propose des résultats reliés à ce problème. Les plus important d’entre eux sont: (1) L’existence de SFT apériodiques vériant une variante de la propriété d’assemblage introduite ici et appelée assemblage linéaire; (2) Une caractérisation des valeurs de l’entropie pour ces SFT (répondant en particulier à une question ouverte de Hochman et Meyerovitch); (3) Une caractérisation d’un seuil pour la calculabilité de l’entropie pour les sous-décalages multidimensionnels à language décidable; (4) Une caractérisation des valeurs possibles de la dimension entropique pour les SFT tridimensionnels minimaux.
Les deux résultats de caractérisation peuvent être interprétés comme une approximation par le haut de classes de SFT optimales sur lesquelles l’entropie (resp. la dimension entropique) peut être calculé uniformément, étendant le domaine dynamique sur lequel un calcul universel peut être implémenté dans les SFT. Le résultat sur le seuil caractérise une classe optimale mais pour les sous-décalage à language décidable, classe un peu plus souple que celle des SFT. Un problème important reste ouvert: celui de trouver une classe optimale pour les SFT multidimensionnels. De plus, on étend le problème à l’intervalle unité, et caractérise les valeurs possibles de l’entropie pour les fonctions calculables de l’intervalle.
–
{{Mots clés :}} sous-décalages, entropie, invariants topologiques, calculabilité.
–
Algorithmic complexity of growth-type invariants of SFT under dynamical constraints
Multidimensional subshifts of nite type (SFT) are sets of colorings of an innite regular grid (Zd,d ≥ 2) dened by local rules. These objects are involved in many areas of mathematics and in particular statistical physics. One important problem in this setting is to compute the entropy with a formula. Unfortunately, it was proved, quite recently, that there can not be a general method to compute (algorithmically) the entropy of these systems. The subsequent approach to the problem is to seek for a subclass on which the entropy can be computed algorithmically. That is the main motivation to study the algorithmical complexity of SFT in subclasses dened by dynamical constraints.
In this text, we expose results related to this problem. The most saliant ones are: (1) The existence of aperiodic subshifts of
Catégories