./.

JAC 2008

À l'occasion du départ à la retraite de mon directeur de thèse Jacques Mazoyer a été organisée une conférence très sérieuse sur les thématiques qui lui sont chères, liées en particulier aux automates cellulaires. De nombreux intervenants extérieurs étaient là (venant de France bien sûr, mais aussi de Finlande, de Russie, d'Italie, du Maroc et du Chili).

Je n'ai mis dans cet article que les photographies de la conférence proprement dites ainsi qu'une analyse personnelle de ce que j'ai appris sur le domaine des automates cellulaires en 2008. L'article détaillé est sur une autre page.

Les automates cellulaires sont un domaine qui est en pleine mutation (et en expansion). On peut distinguer plusieurs thèmes dans les exposés que nous avons vu. Un automate cellulaire, c'est (au sens large) tout un tas de petites cellules qui, toutes en même temps, regardent leurs voisines et changent d'état (de couleur, par exemple : les exposés sur les automates cellulaires sont souvent très colorés). Le changement se fait toujours de la même façon, et pour toutes les cellules simultanément. C'est un très ancien système qui permet de calculer tout ce qu'il est possible de calculer avec un ordinateur, et peut-être même plus... C'est un des premiers modèles de machine parallèle.

Remarque : dans les paragraphes suivants, je ne cite pas tout le monde, et je le sais !

Automates cellulaires et classification algorithmique

C'est un peu la façon ancienne de voir les automates cellulaire, et qui a subi une véritable percée sous l'influence de Jarkko Kari qui a réussi notamment à prouver que l'inversion des automates cellulaires en 2D est indécidable. Les recherches des propriétés dans cette direction, et la généralisation à des sous-classes d'automates cellulaires, continuent bon train. Je mets dedans les travaux d'Ollinger et autres sur l'universalité intrinsèque, par exemple. Jarkko Kari sera probablement responsable de l'organisation de JAC 2010 (en Finlande).

Automates cellulaires et topologie

Principalement emmenée par l'école italienne (Cattaneo et d'autres), il s'agit de regarder le comportement des automates cellulaires en cas de perturbation de la configuration initiale. Les résultats, encore une fois, sont très prometteurs, et amènent des classifications des automates en fonction de leur comportement (auto-stabilisants, chaotiques, etc.).

Automates cellulaires et signaux

Je crois que c'est le point fort de l'approche de Mazoyer et de gens comme Terrier, Durand-Lose ou à une autre époque, moi-même. Il s'agit de faire une relation entre un modèle de calcul AC et un modèle basé sur des signaux qui se rencontrent (et lorsqu'ils se rencontrent, ils peuvent réemettre d'autres signaux, avec des angles définis, etc.). J'ai assisté avec plaisir à une tentative de paléo-informatique (Jean-Baptiste Yunès a tenté de reconstruire la preuve de la synchronisation de la ligne de fusiliers de Goto, perdue complètement, à partir de dessins).

Automates cellulaires et pavages

Avec l'arrivée des tuiles de Wang (comparez cela à des pièces de puzzle non orientables, que l'on ne peut pas tourner du tout) et leur lien avec les automates cellulaires, il est devenu possible de faire une deuxième connexion forte avec des problèmes de géométrie. C'est à ce titre que nous avons eu un exposé de Maurice Nivat, mais c'est aussi le domaine de Bruno Durand (pavages quasi-périodiques, par exemple).

Automates cellulaires et informatique expérimentale

C'est une tactique très explorée et qui donne parfois des résultats théoriques très intéressants : on se limite aux automates cellulaires les plus basiques (cela a beaucoup été fait sur le jeu de la vie, mais les plus sérieux s'intéressent aux 256 automates cellulaires de la classification de Wolfram — deux états, 3 voisins) et on fait des études expérimentales (perturbabilité, universalité, etc.). C'est dans cette lignée que nous avons eu le plaisir d'un exposé d'Éric Golès. Les résultats qu'on arrive à obtenir (j'ai notamment très apprécié un exposé sur de la propagation d'erreur et la synchronisation forcée) sont très surprenants et témoignent de la vitalité d'un domaine qui utilise des outils très abstraits (indécidabilité, hiérarchie de calcul) mais s'accomode aussi d'expérimentations pratiques.

J'aimerais ajouter que les exposés étaient tous d'un excellent niveau. Le mien était toutefois hors-sujet.