Caractérisation des comportements asymptotiques typiques d’automates cellulaires

Benjamin Helloin
I2M, Aix-Marseille Université
https://www.lri.fr/~hellouin/

Date(s) : 06/05/2014 iCal
11 h 00 min - 12 h 00 min

Un automate cellulaire est un système dynamique agissant localement, uniformément et de manière synchrone sur l’espace A^ℤ, où A est un alphabet fini. Il s’agit également d’un modèle de calcul massivement parallèle, et ces deux points de vue s’intersectent de différentes manières.

Nous considérons ici la question du comportement asymptotique après itération sur une configuration initiale aléatoire. Des simulations montrent que ces systèmes présentent une grande variété de comportements typiques, que nous cherchons à caractériser.

Formellement, partant d’une mesure de probabilité initiale simple, on considère les mesures et ensembles de mesures atteignables à la limite. Des conditions nécessaires en termes de calculabilité apparaissent naturellement sur ces ensembles (aspect « modèle de calcul »), et nous montrerons, à l’aide d’une construction explicite, que ces obstructions fournissent en réalité une caractérisation complète.

Suivant le temps et l’interêt exprimé, nous examinerons diverses conséquences de ce résultat et directions de recherche.

Characterization of asymptotic behaviors typical of cellular automata

A cellular automaton is a dynamic system acting locally, uniformly and synchronously on the space A ^ ℤ, where A is a finite alphabet. It is also a massively parallel computing model, and these two views intersect in different ways. We consider here the question of the asymptotic behavior after iteration on a random initial configuration. Simulations show that these systems exhibit a wide variety of typical behaviors, which we seek to characterize. Formally, starting from a simple initial probability measure, we consider the measures and sets of measures attainable at the limit. Necessary conditions in terms of computability appear naturally on these sets (« computational model » aspect), and we will show, using an explicit construction, that these obstructions actually provide a complete characterization. Depending on the time and the interest expressed, we will examine various consequences of this result and directions of research.

Slides: https://members.loria.fr/MHoyrup/Computability/hellouin.pdf

Catégories

Séminaire Ernest