Automates cellulaires surjectifs et mesures de probabilité
Time: 14:00 -- Location: bat 650, 455
summary: Les automates cellulaires sont un modèle de calcul simple consistant en une coloration d'un graphe infini régulier (typiquement, une ligne infinie) sur lequel on itère une transformation locale uniforme. Ce modèle est capable de calcul universel dans un certain sens, y compris quand la configuration initiale est choisie au hasard. Cependant, quand on ajoute la contrainte que l'automate est surjectif, cela amène de fortes contraintes combinatoires sur les comportements possibles de l'automate. Ces contraintes ne sont pas encore complètement comprises et il reste diverses questions ouvertes.
Cet exposé présente deux travaux dans cette direction. Premièrement, je décrirai une famille d'automates ayant des comportements dits randomisants, où le système converge vers un aléa uniforme quelle que soit la manière dont la configuration initiale est choisie (il s'agit donc de systèmes simples, calculatoirement parlant). Deuxièmement, je montrerai des contre-exemples à des conjectures trop naïves sur le comportement de l'automate si on ne met aucune restriction sur l'aléa du choix de la configuration initiale.
Les travaux de cet exposé sont issus de collaborations avec Guillaume Theyssier, Ilkka Törma et Ville Salo.