Discrétisation automatique de ℝ2 vers un automate cellulaireJ. Durand-Lose9 novembre 2012 |
Résumé : Les automates cellulaires sont des systèmes dynamiques à espace et temps discret. Néanmoins, depuis longtemps, les chercheurs ont l’habitude d’expliquer la dynamique par des dessins avec un espace et un temps continus, ou inversement, de partir de conception et de constructions (continues) sur ℝ2 puis de discrétiser pour avoir l’automate cellulaire voulu. Dans un sens le passage au continu est une abstraction utile pour comprendre, dans l’autre, des « détails techniques » sont souvent plus ou moins laissés à la « sagacité du lecteur ».Depuis une dizaine d’années, une contrepartie purement continue (en espace et en temps) aux automates cellulaires, les machines à signaux a été développée. Le but de ce stage est de considérer les possibilités de discrétiser automatiquement des machines à signaux en automates cellulaires tout en préservant diverses propriétés.
Le travail en stage va de l’implantation de discrétisations (et leur étude pragmatique) à des recherches théoriques sur une logique capable d’exprimer des propriétés valables dans le monde discret et continu et voir ce que l’on peut espérer conserver.
Les automates cellulaires sont des systèmes dynamiques massivement parallèles et foncièrement discrets. Leurs configurations sont une ligne de cellule. La dynamique consiste à mettre toutes les cellules à jour en fonction d’une règle commune et de l’état de la cellule et de ses voisines.
L’évolution d’un automate cellulaire se représente graphiquement par l’empilement des configurations successives formant un diagramme espace-temps comme sur les figures suivantes.
Le dessin suivant illustre une même dynamique observée à gauche chez un automate cellulaire et à droite chez une machine à signaux. La grille à gauche correspond à la discrétisation de l’espace et du temps.
Dans toute cette section, le temps va de haut en bas conformément aux illustrations originelles.
Voici une première illustration de la conception dans le continu puis discrétisation (sur le problème de synchronisation des fusiliers Goto [1966]). L’illustration de droite étant une vision moderne avec une machine à signaux.
Un autre exemple, toujours sur le problème de synchronisation, tiré de Varshavsky et al. [1970, Fig 1 and 3].
Plus récent, mais cette fois pour comprendre puis prouver un comportement observé (génération par algorithme génétique d’un automate cellulaire clignotant globalement synchronisé) dans Das et al. [1995].
L’importance des signaux dans les automates cellulaires et le lien avec les machines à signaux est présenté plus particulièrement dans Durand-Lose [2008].
Dans un espace continu unidimensionnel (ℝ), on place un certain nombre de signaux : points sans dimension qui se déplacent de manière rectiligne uniforme. À chaque signal est associé un méta-signal, celui-ci définit toute la dynamique du signal : sa vitesse (constante) et ce qu’il se passe en cas de rencontre avec un autre signal.
Quand des signaux se rencontrent, ils sont enlevés et d’autres signaux apparaissent suivant des règles de collision.
Le comportement des machines à signaux est très complexe et très riche. En effet, on peut calculer au sens des machines de Turing (comme pour les automates cellulaires), mais on peut également calculer sur des valeurs continues avec exactitude [Durand-Lose, 2009] et résoudre le problème de la halte! [Durand-Lose, 2012a].
Comme on peut le deviner sur la figure du milieu, on peut profiter de la continuité de l’espace et du temps pour faire des effets Zénon (comme le paradoxe d’Achille et de la tortue), des accumulations qui imposent des limites à la discrétisation. [Durand-Lose, 2012b]
La dernière figure est une parallélisation fractale permettant de résoudre SAT en temps (durée) constant et temps (enchaînement de collisions) quadratique avec une largeur / espace constante (en tant que longueur) ou exponentielle (en tant que nombre de signaux présents simultanément) [Duchier et al., 2012].
Une courte introduction visuelle aux machines à signaux est accessible sur internet.
Il existe beaucoup de façons de concevoir la discrétisation : plus ou moins brutalement, en passant par un système dynamique intermédiaire ou par la pré-topologie (comme cela a été initié dans Senot and Levorato [2010]).
La discrétisation est une approximation, on ne peut espérer, hors de cas triviaux, récupérer toutes les dynamiques possibles d’une machine à signaux. De là, il faut définir une qualité ou un limite de l’approximation. Par delà, se pose la question de ce qui est exprimé et de comment l’apprécier, voir le décrire avec un langage ad hoc.
À long terme, le projet serait de disposer d’une logique ad hoc permettant de définir des propriétés du comportement d’une machine à signaux sur certaines configurations et de pouvoir faire une discrétisation automatique garantissant ces propriétés cette fois interprétées sur un automate cellulaire. Il s’agirait d’une thèse et non de stage long de master 2.
Les recherches faites dans le cadre de ce stage peuvent être très pratiques (implanter et tester des discrétisations, une bibliothèque java a été développé pour les machines à signaux) ou très théoriques (mettre au point une logique qui ait un sens dans les deux contextes). Il y a bien entendu toute latitude entre ces deux extrêmes.
Le stagiaire bénéficiera d’un portable et d’un bureau au sein du LIFO durant la durée du stage. Le stage est rémunéré (indemnités) et pourrait déboucher sur une thèse.
Mes articles sont accessibles directement sur cette page web.
This document was translated from LATEX by HEVEA.