Benjamin Hellouin
IRIF, Université Paris Diderot
https://www.mat-unab.cl/~hellouin/
Date(s) : 17/03/2015 iCal
11 h 00 min - 12 h 00 min
Je m’intéresse au comportement des automates cellulaires sur une configuration initiale tirée au hasard, ce qui revient à étudier leur action sur l’espace des mesures de probabilité. Je présenterai un panorama de mes recherches sur les mesures limites de ces systèmes, qui peuvent être vues comme leur comportement asymptotique typique ou comme leur sortie en tant qu’algorithme probabiliste.
En dimension 1, les mesures atteignables en partant d’une mesure simple, comme la mesure uniforme, sont entièrement décrivables par des conditions de calculabilité. Porter ce résultat aux dimensions supérieures est un travail en cours qui a déjà donné des résultats partiels. Cependant cette approche de permet pas d’obtenir des mesures limites de support plein, qui ne peuvent être atteintes que par des dynamiques surjectives.
Bien que les automates cellulaires surjectifs soient capables de calcul, leur action sur les mesures possède une forte rigidité qui est encore peu comprise. On conjecture expérimentalement que certaines sous-classes font converger toutes les mesures initiales simples vers la mesure uniforme. Nous produisons la première preuve complète de ce phénomène dans un automate cellulaire ayant des propriétés algébriques particulières, utilisant des structures autosimilaires dans son évolution temporelle.
Limit measurements in cellular automata
I am interested in the behavior of cellular automata on an initial configuration drawn at random, which amounts to studying their action on the space of probability measures. I will present an overview of my research on the limit measures of these systems, which can be seen as their typical asymptotic behavior or as their output as a probabilistic algorithm.
In dimension 1, the measures achievable starting from a simple measure, such as the uniform measure, are entirely describable by conditions of computability. Bringing this result to higher dimensions is a work in progress which has already yielded partial results. However, this approach does not make it possible to obtain limit measurements of full support, which can only be reached by surjective dynamics.
Although surjective cellular automata are capable of computation, their action on measurements has a strong rigidity which is still little understood. We conjecture experimentally that some subclasses converge all the initial simple measures to the uniform measure. We produce the first complete proof of this phenomenon in a cellular automaton with particular algebraic properties, using autosimilar structures in its temporal evolution.
Catégories