# Robustesse des systèmes complexes : étude du rôle de l’aléa dans la dynamique des automates cellulaires

Nazim A. Fatès

<figure><img src="image_1.png" /></figure>

To cite this version:

Nazim A. Fatès. Robustesse des systèmes complexes : étude du rôle de l’aléa dans la dynamique des automates cellulaires. Automates cellulaires et gaz sur réseau [nlin.CG]. Université de Lorraine, 2023. tel-04165486

HAL Id: tel-04165486

https://inria.hal.science/tel-04165486

Submitted on 19 Jul 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Robustesse des systèmes complexes :
## étude du rôle de l'aléa dans la dynamique des automates cellulaires

## THÈSE

présentée et soutenue publiquement le 24 mai 2023

pour l'obtention d'une

Habilitation de l'université de Lorraine

(mention informatique)

par

Nazim FATÈS

### Composition du jury

Rapporteurs :

Bernard DE BAETS
Bernadette CHARRON-BOST
Bastien CHOPARD
professeur à l'université de Gand
directrice de recherche au CNRS, ÉNS Paris
professeur à l'université de Genève

Examinateurs :

Philippe CHASSAING
Enrico FORMENTI
Emmanuel JEANDEL
professeur à l'université de Lorraine
professeur à l'université Côte d'Azur
professeur à l'université de Lorraine
Mis en page avec la classe thesul.
Remerciements

Dans mon pays, les tendres preuves du printemps et les oiseaux mal habillés sont
préférés aux buts lointains.

La vérité attend l'aurore à côté d'une bougie. Le verre de fenêtre est négligé. Qu'im-
porte à l'attentif.

Dans mon pays, on ne questionne pas un homme ému.

Il n'y a pas d'ombre maligne sur la barque chavirée.

Bonjour à peine, est inconnu dans mon pays.

On n'emprunte que ce qui peut se rendre augmenté.

Il y a des feuilles, beaucoup de feuilles sur les arbres de mon pays. Les branches
sont libres de n'avoir pas de fruits.

On ne croit pas à la bonne foi du vainqueur.

Dans mon pays, on remercie.

René Char

En acceptant la tâche de participer au jury, les rapporteurs et examinateurs de cette thèse
m'honorent grandement. Qu'ils reçoivent ici l'expression de ma reconnaissance sincère et, par
avance, de mes remerciements pour leurs remarques qui contribueront à l'amélioration de ce
texte qui n'est que l'esquisse d'un travail à venir, et que nous espérons plus complet.

Les personnes rencontrées lors ce parcours de recherches de plus de vingt ans sont trop
nombreuses pour être saluées individuellement. Qu'il me soit donc permis simplement de dire
que ce sont les nombreux « coups d'aile », les sourires, les paroles bienveillantes, les soins et les
bons conseils qui ont rendu possible cette aventure. Le retrait étant propice à l'éclosion, qu'on
me permette de garder tous ces noms enfouis dans un sillon, afin que germent à l'abri les fruits
issus de l'affection et de l'amitié.
# Sommaire

Introduction 1

Partie I Approche analytique des automates cellulaires asynchrones 7

## Chapitre 1

### Classification des automates cellulaires élémentaires avec mise à jour totalement asynchrone

<table><tr><td>1.1 Définitions</td><td>11</td></tr><tr><td>1.2 Une « mécanique élémentaire » des ACE asynchrones</td><td>13</td></tr><tr><td>1.2.1 Mécanique élémentaire</td><td>16</td></tr><tr><td>1.2.2 Graphe de de Bruijn</td><td>16</td></tr><tr><td>1.2.3 Le tableau des réécritures</td><td>18</td></tr><tr><td>1.2.4 Fonctions potentiels</td><td>18</td></tr><tr><td>1.3 Règles à convergence logarithmique</td><td>19</td></tr><tr><td>1.4 Règles à convergence linéaire</td><td>23</td></tr><tr><td>1.5 Règles à convergence quadratique</td><td>26</td></tr><tr><td>1.6 Règles à convergence exponentielle</td><td>26</td></tr><tr><td>1.7 Règles non convergentes</td><td>30</td></tr></table>

## Chapitre 2

### Récurrence des automates cellulaires élémentaires

<table><tr><td>2.1 Définitions</td><td>34</td></tr><tr><td>2.2 Conditions de non-récurrence</td><td>34</td></tr><tr><td>2.3 Récurrence de dix-huit règles</td><td>35</td></tr><tr><td>2.4 Détermination des classes de récurrence</td><td>35</td></tr><tr><td>2.4.1 Règles avec un nombre de classes de communication exponentiel en n</td><td>36</td></tr><tr><td>2.4.2 Règles avec un nombre linéaire de classes de communication</td><td>36</td></tr><tr><td>2.4.3 Règles avec deux classes de communication</td><td>38</td></tr></table>
<table><tr><td>2.4.4</td><td>Règle avec une unique classe de communication</td><td>38</td></tr><tr><td>2.5</td><td>Questions</td><td>40</td></tr></table>

## Chapitre 3

### Une cartographie de travaux sur la question de l'asynchronisme

<table><tr><td>3.1</td><td>Approches expérimentales</td><td>42</td></tr><tr><td>3.1.1</td><td>Études générales</td><td>43</td></tr><tr><td>3.1.2</td><td>Transitions de phase</td><td>43</td></tr><tr><td>3.1.3</td><td>Coalescence</td><td>44</td></tr><tr><td>3.1.4</td><td>Deux variations de la définition de l'asynchronisme</td><td>45</td></tr><tr><td>3.1.5</td><td>Asynchronisme et bruit</td><td>45</td></tr><tr><td>3.2</td><td>Approches analytiques</td><td>46</td></tr><tr><td>3.2.1</td><td>Classifications à partir de chaînes de Markov</td><td>46</td></tr><tr><td>3.2.2</td><td>Analyse des densités asymptotiques</td><td>47</td></tr><tr><td>3.2.3</td><td>Modèles m-asynchrones</td><td>47</td></tr><tr><td>3.3</td><td>Calculer avec des automates cellulaires asynchrones</td><td>47</td></tr><tr><td>3.3.1</td><td>Simulation de modèles (a)synchrones par des modèles (a)synchrones</td><td>47</td></tr><tr><td>3.3.2</td><td>Dépendance à l'ordre de mise à jour</td><td>48</td></tr><tr><td>3.3.3</td><td>Généralisations</td><td>49</td></tr><tr><td>3.4</td><td>Modéliser avec des automates cellulaires asynchrones</td><td>49</td></tr><tr><td>3.4.1</td><td>Théorie des jeux et écologie</td><td>49</td></tr><tr><td>3.4.2</td><td>Phénomènes de synchronisation physiques et biologiques</td><td>50</td></tr><tr><td>3.4.3</td><td>Résolution de problèmes</td><td>50</td></tr><tr><td>3.5</td><td>Autres systèmes complexes</td><td>51</td></tr><tr><td>3.5.1</td><td>Liens aux systèmes multi-agents</td><td>51</td></tr><tr><td>3.5.2</td><td>Autre modèles</td><td>51</td></tr></table>

<table><tr><td>Partie II</td><td>Approche expérimentale des systèmes complexes</td><td>53</td></tr></table>

## Chapitre 4

### Modèle de Greenberg-Hastings

<table><tr><td>4.1</td><td>Présentation du modèle</td><td>56</td></tr><tr><td>4.2</td><td>Transitions de phase</td><td>57</td></tr><tr><td>4.3</td><td>Robustesse du phénomène</td><td>59</td></tr><tr><td>4.4</td><td>Perturbation de la topologie</td><td>59</td></tr><tr><td>4.5</td><td>Développements analytiques</td><td>61</td></tr></table>
<table><tr><td>4.6</td><td>Problème inverse : diagnostic décentralisé</td><td>63</td></tr></table>

## Chapitre 5

### Un modèle de formation d'essais

<table><tr><td>5.1</td><td>Une première observation</td><td>65</td></tr></table>

<table><tr><td>5.2</td><td>Définition du modèle</td><td>66</td></tr></table>

<table><tr><td>5.2.1</td><td>Invariant du damier</td><td>68</td></tr></table>

<table><tr><td>5.2.2</td><td>Récurrence de la chaîne de Markov</td><td>68</td></tr></table>

<table><tr><td>5.3</td><td>Exploration des motifs stables</td><td>68</td></tr></table>

<table><tr><td>5.4</td><td>Quantification de l'ordre</td><td>68</td></tr></table>

<table><tr><td>5.4.1</td><td>Formation de bandes diagonales</td><td>69</td></tr></table>

<table><tr><td>5.4.2</td><td>Phase avec motifs à damiers</td><td>70</td></tr></table>

<table><tr><td>5.4.3</td><td>Phase d'amas</td><td>72</td></tr></table>

## Chapitre 6

### Turmites

<table><tr><td>6.1</td><td>Des modèles discrets simples</td><td>75</td></tr></table>

<table><tr><td>6.1.1</td><td>Turmites</td><td>76</td></tr></table>

<table><tr><td>6.1.2</td><td>Neuf variations</td><td>77</td></tr></table>

<table><tr><td>6.2</td><td>Fondations</td><td>77</td></tr></table>

<table><tr><td>6.2.1</td><td>Cycles</td><td>79</td></tr></table>

<table><tr><td>6.2.2</td><td>Planeurs</td><td>80</td></tr></table>

<table><tr><td>6.2.3</td><td>Blocages</td><td>81</td></tr></table>

<table><tr><td>Partie III</td><td>Résolution de problèmes inverses</td><td>83</td></tr></table>

## Chapitre 7

### Problème de la classification de la densité

<table><tr><td>7.1</td><td>Formalisation du problème</td><td>86</td></tr></table>

<table><tr><td>7.2</td><td>Structure de l'espace des AC probabilistes</td><td>87</td></tr></table>

<table><tr><td>7.3</td><td>Règles de Fukś et Schüle</td><td>88</td></tr></table>

<table><tr><td>7.4</td><td>Règle de Circulation-Majorité</td><td>91</td></tr></table>

<table><tr><td>7.5</td><td>Structures infinies</td><td>92</td></tr></table>

## Chapitre 8

### Problème de la synchronisation globale

<table><tr><td>8.1</td><td>Formalisation du problème</td><td>96</td></tr></table>
<table><tr><td>8.2</td><td>Propriétés élémentaires</td><td>97</td></tr><tr><td>8.3</td><td>Cas stochastique binaire</td><td>98</td></tr><tr><td>8.4</td><td>Généralisation au cas multicolore</td><td>100</td></tr></table>

Chapitre 9

Modèle bio-inspiré pour le problème du regroupement décentralisé

<table><tr><td>9.1</td><td>Présentation du problème et des travaux reliés</td><td>103</td></tr><tr><td>9.2</td><td>Description du modèle</td><td>105</td></tr><tr><td>9.3</td><td>Observation du phénomène d'agrégation</td><td>106</td></tr><tr><td>9.3.1</td><td>Formation de foyers et effet de pacemaker</td><td>106</td></tr><tr><td>9.3.2</td><td>Explications de la dynamique du modèle</td><td>109</td></tr><tr><td>9.3.3</td><td>Robustesse du modèle</td><td>109</td></tr><tr><td>9.4</td><td>Développements du modèle</td><td>110</td></tr><tr><td>9.4.1</td><td>Problème de l'infotaxie collective</td><td>110</td></tr><tr><td>9.4.2</td><td>Des amibes & des robots</td><td>112</td></tr><tr><td>9.4.3</td><td>Des amibes pour classer des données</td><td>114</td></tr></table>

Ouvertures et pistes de recherche 117

Bibliographie
# Introduction

## Systèmes complexes

La question de l'émergence d'ordre dans les systèmes complexes s'identifie peu ou prou à la question de la *morphogenèse*, telle que l'a posée TURING en 1952 [244] :

**Comment un système constitué d'éléments initialement indifférenciés peut-il s'organiser sans intervention extérieure pour faire apparaître un motif, c'est-à-dire former un tout qui soit plus complexe que la somme de ses parties?**

Ainsi formulée, la question n'a pas encore un sens scientifique : ni le mathématicien ni le physicien ne peuvent s'en emparer telle quelle pour échafauder un système d'explications. Il faut en effet préciser les termes de la question : Comment se définit le système et quels sont ses éléments ? Comment interagissent-ils ? Comment évaluer l'organisation du tout ? Comment s'assurer que l'« extérieur » n'intervient pas, ou peu ? etc.

Les automates cellulaires peuvent être vus comme un moyen pour aborder cette question, pour l'aborder de manière *radicale* pourrait-on ajouter. Ce modèle mathématique nous permet de définir des systèmes constitués d'éléments discrets appelés *cellules* ; ces éléments sont disposés sur une grille régulière et interagissent de façon locale à chaque pas de temps. Cette localité se définit à l'aide d'une fonction appelée *voisinage* qui dit comment chaque cellule est liée à un ensemble fixe de cellules proches, déterminées par une relation uniforme (le même voisinage relatif est appliqué partout). Classiquement, les interactions surviennent de manière synchrone, c'est-à-dire que toutes les cellules changent d'état en même temps. Les cellules ont un espace d'états fini, et on suppose généralement que cet espace est « petit », voire « minimal », c'est-à-dire que les règles d'interaction entre cellules ne sont pas obtenues par passage du continu au discret mais par une prise en compte directe des transformations entre états.

Le recueil le plus connu du poète Francis Ponge s'intitule *Le parti pris des choses*. On pourrait dire par analogie que l'utilisation d'automates cellulaires pourrait s'appeler *le parti pris discret des choses*, ou, plutôt, un parti pris discret de la modélisation. Depuis les années 1950 et les travaux fondateurs de von Neumann et Ulam [250], les travaux sur ce modèle de calcul se sont développés dans de nombreuses directions. Pour une classification grossière des travaux sur ce thème, nous proposons de distinguer trois types de questions :

1. Celles touchant aux propriétés calculatoires du modèle. L'automate cellulaire est vu comme une machine à calculer reliant des entrées et des sorties. On cherche alors à faire des calculs autrement qu'avec une machine de Turing; le parallélisme et la localité permettent notamment de s'approcher de ce qu'on observe dans la nature, où de nombreux éléments interagissent en vue d'une fin commune.

2. Celles qui se rapportent à la théorie des systèmes dynamiques. Les automates cellulaires sont vus comme des objets qui évoluent dans un espace structuré. De nombreuses questions peuvent être posées sur la dynamique : on peut par exemple analyser si les tra-
<figure><img src="image_3.png" /><figcaption>FIGURE 1 – Diagrammes espace-temps de quatre automates cellulaires correspondant aux quatre classes de Wolfram. Le temps va du bas vers le haut. Les carrés blancs et bleus représentent les états 0 et 1, respectivement.</figcaption></figure>

jectoires partant d'un ensemble de configurations initiales données sont périodiques, chaotiques ou complexes, et chercher à comprendre comment la forme de la règle locale induit tel ou tel type de comportement. L'esprit général consiste à rechercher les propriétés qui permettent de décrire comment l'automate cellulaire parcourt l'espace des configurations au cours de son évolution et la « forme » des trajectoires obtenues.

3. Celles qui sont en lien avec des problèmes de modélisation. On voit alors les automates cellulaires comme un moyen privilégié de simplifier une situation réelle, issue de l'observation d'un système naturel ou artificiel. Les simplifications radicales opérées ne visent pas à rendre compte fidèlement du réel observé mais plutôt à en donner une version simplifiée mais non triviale. L'observateur, par le biais de simulations numériques et d'études analytiques cherche à expliquer comment les lois qu'il a introduites au niveau local produisent tel ou tel comportement qualitatif au niveau global.

## La question de la complexité

Depuis les années 1970, les automates cellulaires ont donné lieu à un foisonnement de questions liées à la complexité algorithmique. En effet, on sait que ce modèle de calcul étant universel au sens Turing, aucune question ne sera décidable en toute généralité (analogue du théorème de Rice). En revanche, que se passe-t-il quand on se restreint à des familles particulières de règles, par exemple en fixant la dimension ou le nombre d'états, ou lorsque l'on ne considère que des configurations finies ? Prenons par exemple le problème suivant :

Prédécesseur AC

Entrée : Un automate cellulaire $F$ (règle globale) et une configuration $x$ finie

Question : Existe-t-il un antécédent $a$ tel que $F(a) = x$ ?

On sait que la version unidimensionnelle de ce problème est dans la classe P alors qu'en dimension supérieure ou égale à deux, le problème est NP-complet (voir par exemple l'ouvrage de Moore et Mertens [172], p. 159). Les questions de complexité algorithmique cherchent à relier la quantité de calculs à effectuer en fonction de la taille de l'entrée. On constate qu'il est
assez aisé de rencontrer des questions difficiles, même si l'on se restreint à d'espaces de règles simples : par exemple on s'est longtemps interrogé pour savoir s'il existait un *automate cellulaire élémentaire*<fnref n="1" /> qui soit universel au sens de Turing. Autre exemple : jusqu'à présent, on ne sait pas décider de la périodicité de la suite binaire générée par la colonne centrale d'un automate cellulaire élémentaire particulier (règle n°30) quand on part d'une configuration qui contient un unique 1. Les lecteurs qui souhaitent en savoir plus sur ce sujet peuvent se rapporter au site de Wolfram où ce problème, reprécisé selon trois questions différentes, a été dotée de trois prix de dix mille dollars chacun<fnref n="2" />.

Les problèmes liés à la théorie de la complexité algorithmique cherchent à examiner les différences entre les modèles de calculs classiques séquentiels et le parallélisme massif des automates cellulaires. On peut par exemple développer une notion d'universalité plus forte, appelée *universalité intrinsèque*, car, sur une grille infinie, on dispose d'une infinité de processeurs pouvant chacun effectuer un calcul local à chaque pas de temps [187].

Plutôt que de chercher à décrire précisément le comportement de chaque règle, on peut également chercher à les regrouper selon diverses catégories de comportement : c'est la question de la *classification* des automates cellulaires. La figure 1 montre quatre diagrammes espacetemps d'automates cellulaires élémentaires. Même si l'on ne connaît pas le détail des règles qui ont généré ces images, on perçoit intuitivement qu'elles correspondent à des comportements qualitatifs différents. À la suite de la définition informelle de ces quatre classes par Wolfram en 1984 [38], différentes tentatives de formalisation sont apparues, dont la plus fameuse est sans doute celle proposée par Kůrka en 1997 [142]. S'il est bien sûr hors de portée de décider de l'appartenance de toute règle aux classes ainsi définies formellement, on peut néanmoins tenter d'avoir des classifications complètes pour des espaces de règles *restreints* : de façon surprenante, il a fallu attendre 2012 et le travail rigoureux et précis de Schüle et Stoop pour disposer enfin d'une classification complète des 256 automates cellulaires élémentaires (ACE) selon les critères de Kůrka [227].

On constate donc que les difficultés sont nombreuses pour parvenir à bâtir une théorie unifiée des automates cellulaires, qui permettrait d'analyser le comportement d'une règle en partant de sa définition locale. Une autre approche consiste à décrire le comportement des automates cellulaires à l'aide de simulations numériques, mais cette façon de faire laisse le mathématicien insatisfait, notamment parce qu'elle revêt toujours un caractère partiel : sur combien d'observations s'appuie-t-on? Comment les paramètres des simulations ont-ils été choisis ? etc.

## Position de notre travail : la question de la robustesse

Par son caractère simplificateur, l'utilisation d'un automate cellulaire, que ce soit pour comprendre les effets du parallélisme massif, pour modéliser un phénomène ou pour inventer une nouvelle méthode de calcul, relève donc toujours d'un parti pris. Comme l'ont exprimé plusieurs auteurs, la difficulté est de savoir quand on fait une observation « quelle part est due à la structure discrète du modèle et quelle part est due aux règles locales » [37]. Autrement dit, que se passe-t-il si les *hypothèses structurelles* du modèle sont modifiées tout en gardant la règle locale inchangée ? Le système va-t-il changer du tout au tout ou observera-t-on un effet modéré de ces perturbations, voire pas d'effet du tout sur le long terme ?

<footnote n="1">1. Un automate cellulaire élémentaire est défini avec une règle unidimensionnelle à états binaires et un voisinage constitué de la cellule et de ses deux voisines immédiates. Voir le paragraphe 1.1 p. 11.</footnote>

<footnote n="2">2. http://rule30prize.org/</footnote>
Nous regroupons ces interrogations sous le terme générique de *question de la robustesse*. Cette question forme le cœur de notre travail et motive notre recherche. Ce mémoire aborde cette question en étudiant un certain nombre de cas simples et vise, autant que faire se peut, à dégager quelques observations clés pour éclairer le problème. Nous regarderons ce qui se produit si l'on ne travaille plus sur une grille régulière, si les transitions des cellules ne sont plus synchrones, si ces transitions sont perturbées par un bruit, etc.

Comme pour la question de la complexité, on se gardera de toute prétention à la généralité : même après une vingtaine d'années de recherches, nous sommes bien loin de disposer d'une théorie qui nous permettrait d'unifier les observations. Notre objectif devra donc être modeste et se borner à quelques explorations en vue d'essayer d'identifier les limites des différentes approches, en particulier savoir quand l'utilisation de l'analyse mathématique est pertinente et quand il est préférable de recourir aux simulations numériques. Notre souhait est que ce travail puisse préparer le terrain aux personnes qui souhaiteront poursuivre cette aventure scientifique. Ce mémoire vise donc avant tout à effectuer un passage de relai, et nous déléguons ainsi la tâche d'explorer plus à fond la question de la robustesse à nos « neveux », suivant ainsi une longue tradition initiée par « ce cavalier français parti d'un si bon pas »<fnref n="3" /> :

> Et j'espère que nos neveux me sauront gré, non seulement des choses que j'ai ici expliquées, mais aussi de celles que j'ai omises volontairement, afin de leur laisser le plaisir de les inventer.

R. Descartes, *La géométrie*

<footnote n="3">3. Charles PÉGUY, *Note conjointe sur M. Descartes et la philosophie cartésienne*.</footnote>
# Plan du mémoire

Ce mémoire est divisé en trois parties, elles-mêmes divisées en trois chapitres.

La première partie est consacrée à traiter l'approche analytique. Nous nous concentrons sur l'analyse des effets de la mise à jour asynchrone des automates cellulaires. Nous présentons tout d'abord les résultats que nous avons établis sur la dynamique asynchrone des automates cellulaires élémentaires (chap. 1) avec une mise à jour totalement asynchrone, c'est-à-dire quand une unique cellule est choisie pour être mise à jour à chaque pas de temps. Nous étudions ensuite (chap. 2) les propriétés de récurrence de ces systèmes, c'est-à-dire leur propension à revenir à leur état initial. Le chapitre 3 présente un état de l'art partiel, qui permettra de faire connaître aux lecteurs un ensemble de recherches liées aux problèmes posés par une mise à jour non synchrone des cellules.

Dans la deuxième partie, nous abordons l'approche expérimentale à l'aide de simulations numériques. Nous cherchons à savoir quels sont les aspects de la robustesse des systèmes complexes qu'il est préférable d'aborder en observant le comportement des modèles plutôt qu'en cherchant à établir une description analytique exacte. Le premier volet est le chapitre 4 ; il concerne le phénomène de réaction-diffusion modélisé avec l'automate cellulaire de Greenberg-Hastings. Le chapitre 5 présente le phénomène de formation d'essais et sa modélisation avec un automate cellulaire de gaz sur réseaux (lattice-gas cellular automata). Nous présentons ensuite une étude d'un système multi-agent « ultra-simple » avec le modèle des turmites, également appelées fourmis de Langton (chap. 6).

La troisième partie traite du rôle de l'aléa pour la résolution de problèmes inverses. Dans cette approche, on se donne une tâche à résoudre et on cherche à trouver des automates cellulaires qui apportent une solution de manière stricte ou approchée. Le premier problème traité est le problème de la classification de la densité (chap. 7). Nous montrons que les automates cellulaires stochastiques permettent d'obtenir des solutions aussi proches que l'on souhaite d'une solution parfaite, alors même qu'il n'existe justement pas de solution parfaite. Dans le chapitre 8, nous présentons le problème de la synchronisation globale, où, là encore, l'aléa permet d'obtenir des solutions simples et dont on peut quantifier la dynamique à l'aide des outils analytiques vus dans la première partie. Enfin, dans le chapitre 9 nous quittons le monde des automates cellulaires stricts pour aborder ce qui est plus un « système de particules », voire un « système multi-agent réactif ». Ce modèle, inspiré du comportement de l'amibe sociale Dictyos telium discoideum, permet de regrouper un grand nombre de particules initialement dispersées de manière décentralisée et avec des interactions locales et simples.

Le mémoire se clôt sur quelques remarques permettant de mettre en perspective nos recherches : nous proposons un florilège de questions qui émanent des différents thèmes explorés. Il ne s'agit évidemment d'une sélection partielle, que les lecteurs compléteront à leur guise, à leur discrétion avons-nous envie de dire...
Première partie

# Approche analytique des automates
cellulaires asynchrones
<figure><img src="image_4.png" /></figure>
# 1

# Classification des automates cellulaires élémentaires avec mise à jour totalement asynchrone

Ce chapitre présente un résumé des travaux en lien avec la classification des automates cellulaires asynchrones, publiés dans actes de conférences ou des revues [97, 75, 78]. À la suite d'une invitation à faire paraître un tutoriel sur le sujet, ils ont été synthétisés dans un article paru en 2020 [87], article dont nous reprenons ici la structure en l'allégeant.

Nous commençons notre voyage au sein des automates cellulaires par une question touchant à leur classification. Les 256 règles que nous allons examiner forment la famille la plus étudiée du domaine. Nous présentons différents résultats ayant trait à leur comportement avec une mise à jour totalement asynchrone. Dans une approche strictement concentrée sur la question de la robustesse, on aurait aimé pouvoir graduellement passer du cas synchrone au cas asynchrone, par exemple en utilisant le mode α-synchrone avec un taux de synchronisme diminuant de façon continue. Malheureusement, l'obtention de résultats analytiques pour ce cas est extrêmement difficile et conduit à des phénomènes curieux comme des transitions de phase. Aussi, nous nous contentons ici de présenter le cas extrême où une seule cellule est mise à jour à chaque pas de temps. Comme nous allons le voir, cela simplifie les choses mais sans les rendre triviales, loin de là.
<table><caption>TABLE 1.1 – Règles démontrées ou conjecturées logarithmiques selon le PTCM.</caption><thead><tr><th>diag.</th><th>diag.</th><th>Wcode</th><th>Tcode</th><th>01</th><th>10</th><th>101</th><th>010</th><th>conv.</th></tr></thead><tbody><tr><td></td><td></td><td>0</td><td>EFGH</td><td>→</td><td>←</td><td>]0[</td><td>*1*</td><td>LOG</td></tr><tr><td></td><td></td><td>2</td><td>BEFGH</td><td>↔</td><td>←</td><td>]0[</td><td>*1*</td><td>LOG</td></tr><tr><td></td><td></td><td>4</td><td>FGH</td><td>→</td><td>←</td><td>]0[</td><td>]1[</td><td>LOG</td></tr><tr><td></td><td></td><td>5</td><td>AFGH</td><td>→</td><td>←</td><td>]0[</td><td>]1[</td><td>LOG</td></tr><tr><td></td><td></td><td>8</td><td>EGH</td><td>.</td><td>←</td><td>]0[</td><td>*1*</td><td>LOG</td></tr><tr><td></td><td></td><td>10</td><td>BEGH</td><td>←</td><td>←</td><td>]0[</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>12</td><td>GH</td><td>.</td><td>←</td><td>]0[</td><td>]1[</td><td>LOG</td></tr><tr><td></td><td></td><td>13</td><td>AGH</td><td>.</td><td>←</td><td>]0[</td><td>]1[</td><td>LOG</td></tr><tr><td></td><td></td><td>18</td><td>BCEFGH</td><td>↔</td><td>↔</td><td>]0[</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>24</td><td>CEGH</td><td>.</td><td>↔</td><td>]0[</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>26</td><td>BCEGH</td><td>←</td><td>↔</td><td>]0[</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>32</td><td>DEFGH</td><td>→</td><td>←</td><td>*0*</td><td>*1*</td><td>LOG</td></tr><tr><td></td><td></td><td>34</td><td>BDEFGH</td><td>↔</td><td>←</td><td>*0*</td><td>*1*</td><td>LOG</td></tr></tbody></table>
<figure><img src="image_5.png" /><figcaption>FIGURE 1.1 – Représentation d’une configuration sur $Z/12Z$ en anneau et en ligne.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>FIGURE 1.2 – Représentation de la fonction de transition d’un ACE.</figcaption></figure>

# 1.1 Définitions

Un automate cellulaire élémentaire (ACE) est un automate cellulaire binaire, unidimensionnel, avec un voisinage $V = \{-1, 0, 1\}$.

Nous nous intéressons ici au cas *fini* et l'on supposera que les cellules sont disposées en anneau. L'ensemble des cellules est donc représenté par $\mathcal{L} = \mathbb{Z}/n\mathbb{Z}$.

L'état de l'automate à un instant donné est appelé une *configuration* ; l'ensemble des configurations est noté $\mathcal{E}_n = \{0, 1\}^\mathcal{L}$, il correspond ici à l'ensemble des états des cellules (voir figure 1.1).

L'évolution d'un ACE est gouvernée par sa fonction de transition locale $f : \{0, 1\}^3 \to \{0, 1\}$. Cette fonction dicte comment une cellule met à jour son état en fonction de son état propre et des états des cellules de droite et de gauche.

On appelle *transition* la relation entre un triplet d'états $(g, m, d)$ et la valeur $f(g, m, d)$, où par convention $g, m, d$ sont respectivement l'état de la cellule à gauche, l'état de la cellule mise à jour et l'état de la cellule à droite (cf. fig. 1.2). Si $f(g, m, d) \neq m$ la transition est *active* et dans le cas contraire elle sera dite *passive*. Par extension, pour une configuration $x$ donnée, on dira qu'une cellule $i \in \mathcal{L}$ est *active* ou *passive* selon que la transition qui s'applique en $i$ est respectivement active ou passive.

## Mode totalement asynchrone

Nous nous intéressons ici au cas où un automate cellulaire est mis à jour de façon *totalement asynchrone*, c'est-à-dire qu'une seule cellule est mise à jour à chaque pas de temps ; cette cellule est tirée au hasard de manière uniforme et sans mémoire d'un pas de temps au suivant.

On dénote par $(U_t)_{t \in \mathbb{N}} \in \mathcal{L}^\mathbb{N}$ la suite de cellules qui sont tirées pour être mises à jour. L'évolution d'un ACE est donnée par la suite de configurations $(x^t)_{t \in \mathbb{N}}$ ainsi définies : $x^0 = x$ et
$x^{t+1} = F(x, U_t)$, avec :

$$ \forall i \in \mathcal{L}, \quad x_i^{t+1} = \begin{cases} f(x_{i-1}^t, x_i^t, x_{i+1}^t) & \text{si } i = U_t \\ x_i^t & \text{sinon.} \end{cases} \qquad (1.1) $$

Dans notre cas, on considère que $(U_t)$ est une suite de variables aléatoires indépendantes qui tirent un élément de manière uniforme dans $\mathcal{L}$. Comme la suite $(U_t)$ est connue, on se contentera d'écrire simplement $x^{t+1} = F(x^t)$ pour décrire l'évolution du système à partir de la configuration $x^t$. On considère que $(x^t)$ est un processus stochastique, c'est-à-dire que chaque $x^t$ est une variable aléatoire. Cette notation simplifie les choses mais n'est pas tout à fait ri-goureuse; elle cache en effet les difficultés inhérentes à la définition des variables aléatoires en théorie des probabilités. Pour une définition plus canonique de ces objets, on pourra par exemple se rapporter à un article de Marcovici et Mairesse où les automates cellulaires sont définis en termes de transformations sur des distributions définies « proprement » à l'aide de la théorie de la mesure [162].

## Critère de classification

Une configuration $x \in \mathcal{E}_n$ est appelée *point fixe* si la relation $F(x) = x$ est un événement certain. Ceci revient à dire que toutes les cellules sont passives. On note $\mathbb{F}$ l'ensemble des points fixes.

On remarquera que la propriété d'être un point fixe est indépendante du mode de mise à jour : en effet, si une configuration n'est constituée que de cellules passives, mettre à jour tout ou partie des cellules ne change rien. L'ensemble des points fixes est donc conservé lors du passage du synchrone à l'asynchrone.

Notre but est ici de classer les automates cellulaires en fonction du temps moyen mis pour atteindre un point fixe. On note $T(x)$ la variable aléatoire qui correspond au temps mis pour atteindre un point fixe :

$$ T(x) = \min\{t \in \mathbb{N}, x^t \in \mathbb{F}\}. $$

Lorsque le système n'atteint jamais de point fixe, cette valeur vaut l'infini.

On remarque que si l'on souhaite comparer les modes de mise à jour synchrone et asynchrone, il peut être intéressant de considérer qu'une unité de temps en mode totalement synchrone correspond à $n$ pas de temps en mode asynchrone. On examinera donc de préférence un temps de convergence rééchelonné (rescaled en anglais), obtenu en divisant $T(x)$ par $n$.

Pour une taille d'anneau donnée $n$, on définit le *pire temps de convergence moyen* (PTCM) selon :

$$ \tau(n) = \frac{1}{n} \max_{x \in \mathcal{E}_n} \mathbb{E}\{T(x)\}. $$

Autrement dit, nous nous intéressons à la valeur maximale du temps de convergence rééchelonné pour toutes les configurations d'une taille donnée. Lorsque la limite de $\tau(n)$ pour $n$ grand n'existe pas, on dira que l'automate est *non convergent*.

Notre objectif est de trouver comment se comporte $\tau(n)$ pour les 256 automates cellulaires élémentaires. L'intuition qui motive cette étude est que le comportement qualitatif de l'automate influera la façon dont $\tau$ varie avec le nombre de cellules $n$. On espère donc trouver des familles de comportement qui permettent de séparer de manière analytique les différentes classes de règles.
<figure><img src="image_7.png" /><figcaption>FIGURE 1.3 – Illustration des symétries des automates cellulaires.</figcaption></figure>

Rappelons les notations usuelles : $\tau(n) \in \mathcal{O}(\phi(n))$ signifie que $\phi$ majore $\tau$ à une constante près, et $\tau(n) \in \mathcal{Theta}(\phi(n))$ signifie que $\phi$ minore $\tau$ à constante près et majore $\tau$ à une constante près.

Par souci de simplicité, on emploiera parfois simplement le terme de *temps de convergence* pour parler de $\tau$ dans la suite.

<table><caption>TABLE 1.3 – Notation par transitions: lettres associées à chaque transition active.</caption><thead><tr><th>A</th><th>B</th><th>C</th><th>D</th></tr></thead><tbody><tr><td>000</td><td>001</td><td>100</td><td>101</td></tr><tr><td>010</td><td>011</td><td>110</td><td>111</td></tr><tr><td>E</td><td>F</td><td>G</td><td>H</td></tr></tbody></table>

## 1.2 Une « mécanique élémentaire » des ACE asynchrones

En suivant une convention introduite par Wolfram, nous désignerons chaque ACE $f$ par un code décimal $W(f)$ obtenu en convertissant les bits de la table de transition de $f$ en un nombre compris entre 0 et 255 : $W(f) = f(0, 0, 0) \cdot 2^0 + f(0, 0, 1) \cdot 2^1 + \dots + f(1, 1, 1) \cdot 2^7$.

En complément, nous introduisons une autre représentation des ACE, que nous appelons le *code par transitions*, qui consiste à désigner un ACE $f$ avec un mot formé des lettres $\{A, B, \dots, H\}$, où chaque lettre dénote une *transition active* de la règle. La correspondance entre les lettres et les transitions est donnée dans la table 1.3.

*Exemple 1.* Considérons la règle du XOR $f(x, y, z) = x \oplus y \oplus z$, où $\oplus$ désigne le ou exclusif. Le code décimal associé à cette règle est 150. Ses transitions actives sont : $001 \rightarrow 1$ (B), $100 \rightarrow 1$ (C), $011 \rightarrow 0$ (F), $110 \rightarrow 0$ (G), ce qui donne comme code par transitions : BCFG.

### Symétries des ACE

Un point important qui concerne les automates cellulaires est la connaissance des symétries qui ne modifient pas leurs propriétés globales.

La première de ces symétries est la *réflexion*, où l'on échange les directions droite et gauche. Notons par $R : \mathcal{E}_n \rightarrow \mathcal{E}_n$ la fonction qui opère sur les configurations et telle que : $\forall x \in \mathcal{E}_n, y =$
$R(x) \implies \forall i \in \mathcal{L}, y_i = x_{n-1-i}$. Pour une fonction locale $f(x, y, z)$ et on définit le symétrique par réflexion de $f$ par $f^R(x, y, z) = f(z, y, x)$. Si $F$ et $F^R$ sont les fonctions globales associées respectivement à $f$ et $f^R$, alors on a $R \circ F = F^R \circ R$ et $F^R = R \circ F \circ R$. Autrement dit, partant d'une configuration donnée, il est équivalent de regarder l'image de cette configuration par $F$ dans un miroir ou de regarder l'image de $F^R$ sur la configuration retournée par un miroir.

Il en va de même pour la symétrie de conjugaison, que l'on définit selon : $\forall x \in \mathcal{E}_n, y = C(x) \implies \forall i \in \mathcal{L}, y_i = 1 - x_i$. La règle locale conjuguée de $f$ est $f^C(x, y, z) = 1 - f(1-x, 1-y, 1-z)$. Là aussi, on a l'invariance suivante : $C \circ F = F^C \circ C$ qui s'écrit aussi : $F^C = C \circ F \circ C$. Autrement dit, regarder l'effet de $F$ à l'aide de « lunettes inversant les couleurs » est équivalent à regarder l'effet de $F^C$ sur la configuration dont les couleurs ont été inversées.

On peut évidemment combiner les deux symétries pour en obtenir une troisième, la réflexion-conjugaison, et l'on obtient la règle locale $f^+(x, y, z) = 1 - f(1-z, 1-y, 1-x)$ en appliquant les deux symétries correspondantes.

Connaissant le code décimal de Wolfram d'une règle $f$, il n'est pas immédiat de trouver le code de Wolfram des règles symétriques : sauf cas particulier, il faut écrire la table de transition, puis lui opérer la symétrie et recalculer le nouveau code décimal. En revanche, avec le code par transitions, l'obtention des symétriques est direct : la réflexion est obtenue en permutant les couples de lettres B et C (c'est-à-dire en remplaçant le B par un C et le C par un B) et en permutant les couples F et G; la conjugaison est obtenue en échangeant les lettres selon les couples suivants : A et H, B et G, C et F, et, D et E. La réflexion-conjugaison est quant à elle obtenue en combinant ces deux opérations. Ces opérations sont représentées sur la figure 1.3.

Pour connaître les nombre de classes d'équivalence de ces symétries, nous procédons à un dénombrement simple. Il existe $2^6 = 64$ règles invariantes par réflexion, $2^4 = 16$ règles invariantes par conjugaison, $2^6 = 16$ règles invariantes par réflexion-conjugaison. Il existe $2^3 = 8$ règles invariantes par réflexion et par conjugaison. Nous avons donc $64 - 8 = 56$ règles invariantes par $R$ uniquement, $16 - 8 = 8$ règles invariantes par $C$ uniquement et, $16 - 8 = 8$ règles invariantes par $R \circ C$ uniquement. Le nombre de règles qui ne sont pas invariantes par $R$ ou $C$ est $256 - (56 + 8 + 8 + 8) = 176$. Ceci nous permet d'affirmer que le nombre de classes d'équivalence est $176/4 + 56/2 + 8/2 + 8/2 + 8/1 = 44 + 28 + 4 + 4 + 8 = 88$.

Dans le reste du texte, nous examinerons une règle par classe d'équivalence, choisie comme étant celle qui a le plus petit code de Wolfram : nous parlons alors d'automate cellulaire élémentaire minimal.
<table><caption>TABLE 1.2 – Règles démontrées ou conjecturées logarithmiques selon le PTCM.</caption><thead><tr><th>diag.</th><th>diag.</th><th>Wcode</th><th>Tcode</th><th>01</th><th>10</th><th>101</th><th>010</th><th>conv.</th></tr></thead><tbody><tr><td></td><td></td><td>36</td><td>DFGH</td><td>→</td><td>←</td><td>*0*</td><td>]1[</td><td>LOG?</td></tr><tr><td></td><td></td><td>40</td><td>DEGH</td><td>.</td><td>←</td><td>*0*</td><td>*1*</td><td>LOG</td></tr><tr><td></td><td></td><td>42</td><td>BDEGH</td><td>←</td><td>←</td><td>*0*</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>44</td><td>DGH</td><td>.</td><td>←</td><td>*0*</td><td>]1[</td><td>LOG?</td></tr><tr><td></td><td></td><td>50</td><td>BCDEFGH</td><td>↔</td><td>↔</td><td>*0*</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>56</td><td>CDEGH</td><td>.</td><td>↔</td><td>*0*</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>58</td><td>BCDEGH</td><td>←</td><td>↔</td><td>*0*</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>72</td><td>EH</td><td>.</td><td>.</td><td>]0[</td><td>*1*</td><td>LOG</td></tr><tr><td></td><td></td><td>76</td><td>H</td><td>.</td><td>.</td><td>]0[</td><td>]1[</td><td>LOG</td></tr><tr><td></td><td></td><td>77</td><td>AH</td><td>.</td><td>.</td><td>]0[</td><td>]1[</td><td>LOG</td></tr><tr><td></td><td></td><td>104</td><td>DEH</td><td>.</td><td>.</td><td>*0*</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>106</td><td>BDEH</td><td>←</td><td>.</td><td>*0*</td><td>*1*</td><td>LOG?</td></tr><tr><td></td><td></td><td>200</td><td>E</td><td>.</td><td>.</td><td>]0[</td><td>*1*</td><td>LOG</td></tr><tr><td></td><td></td><td>232</td><td>DE</td><td>.</td><td>.</td><td>*0*</td><td>*1*</td><td>LOG</td></tr></tbody></table>
## 1.2.1 Mécanique élémentaire

La notation par transitions va nous permettre d'analyser la dynamique des automates cellulaires asynchrones. Notre but est de mettre en place une sorte de « mécanique élémentaire » qui permettra d'analyser le comportement des 88 ACE minimaux.

Pour une configuration donnée, nous appelons une *q*-région un ensemble maximal de cel- lules adjacentes dans l'état *q*. Les *frontières* sont les cellules qui séparent deux régions.

Les lois de mécanique élémentaire peuvent se formuler ainsi :

- Si une transition A (resp. H) est *passive*, la taille d'une 0-région (resp. d'une 1-région) peut croître ou décroître mais cette région ne peut être brisée en deux.

- Les transitions B et F contrôlent les mouvements des frontières 01 : B (resp. F) déplace cette frontière à gauche (resp. à droite). Si les deux transitions sont actives, la frontière 01 se déplace selon une marche aléatoire non biaisée.

- Symétriquement, les transitions C et G commandent les déplacements des frontières 10.

- La transition D conditionne la fusion des 1-régions : l'absence de D implique que les 0-régions ne peuvent pas disparaître. De même, les 1-régions ne peuvent disparaître que si E est active.

Ces propriétés sont résumées dans la table 1.4.

Nous recommandons fortement aux lecteurs d'avoir une copie du tableau 1.3 et de ces règles devant eux. En effet, la majeure partie des démonstrations qui suivront s'appuient sur ces éléments.

## 1.2.2 Graphe de de Bruijn

Le code par transitions que nous avons présenté ci-dessus (cf. tableau 1.3) est défini par une application $t : Q^3 \to \{a, \dots, h\}$. Cette application sera utilisée pour nous donner une vue complémentaire des configurations; pour cela, on associe à une configuration $x \in Q^\mathcal{L}$ une configuration $\tilde{x} \in \{a, \dots, h\}^\mathcal{L}$, l'image $T$ de $x$; obtenue en associant à chaque cellule une étiquette a, b, ... selon que la transition A, B, ... s'y applique (indépendamment du fait que cette transition soit active ou non). Nous écrirons $x \stackrel{t}{=} \tilde{x}$ pour signifier que $\tilde{x} = t(x)$ est l'image $T$ de $x$. Un exemple de transformation des configurations et leurs images $T$ est donné sur la figure 1.4.

Cette transformation peut se faire directement mais il est également intéressant de considérer le graphe de de Bruijn (cf. fig. 1.5), qui permet de faire cette transformation en lisant un symbole binaire après l'autre en parcourant le graphe en suivant l'arc qui correspondant au symbole binaire qui a été lu.

<caption>TABLE 1.4 – **à gauche** : Description synthétique des effets de chaque transition dans les ECA. **à droite** : Effets des combinaisons de deux transitions.</caption>

A 0-régions instables
B dépl. à gauche des frontières 01
C dépl. à droite des frontières 10
D disparitions des 0-régions
E disparitions des 1-régions
F dépl. à droite des frontières 01
G dépl. à gauche des frontières 10
H 1-régions instables

ni A ni H règles doublement quiescentes

B+ F marche aléatoire des frontières 01

C+ G marche aléatoire des frontières 10
0011001111100
abfgcbfhhhgca
↑
0011001011100
abfgcbedfhgca

FIGURE 1.4 – Exemple de deux configurations binaires et de leurs images T. La configuration du haut est obtenue par la mise à jour de la cellule de la configuration du bas indiquée par une flèche.

<figure><img src="image_8.png" /></figure>

FIGURE 1.5 – Graphe de de Bruijn construit selon la correspondance entre séquences binaires de longueur 3 et les transitions A, ..., H. Les étiquettes sur les arcs montrent la valeur donnée en entrée lorsque l'on lit une séquence de gauche à droite.
Ce graphe permet de déterminer diverses propriétés des automates cellulaires. En particulier, on peut d'ores et déjà noter que puisque les configurations sont définies sur un anneau $(\mathbb{Z}/n\mathbb{Z})$, les points fixes d'une règle sont les configurations pour lesquelles un circuit dans le graphe de de Bruijn ne passe jamais par un nœud avec une transition active.

Pour une configuration particulière $x \in \mathcal{E}_n$, nous notons par $a(x), \dots, h(x)$ le nombre d'occurrences des étiquettes a, ..., h dans $\tilde{x}$, l'image T de $x$. Notons que dans la plupart des cas, l'argument $x$ sera omis pour les fonctions $a, \dots, h$ puisqu'il sera donné implicitement par le contexte.

Pour un motif $P \in \mathcal{Q}^*$, notons $|x|_P$ le nombre d'occurrences de $P$ dans $x$. Nous avons alors :

$$ b = c, \quad f = g, \tag{1.2} \\ |x|_{01} = b+d=c+d=e+f=e+g=|x|_{10}. $$

Ces équations nous permettront de transformer diverses expressions afin de quantifier les temps de convergence.

### 1.2.3 Le tableau des réécritures

<table><caption>TABLE 1.5 – Tableau des réécritures des 32 triplets des images T. Les colonnes correspondent aux huit étiquettes pour la cellule centrale, les lignes aux quatre étiquettes possibles à gauche et à droite.</caption><thead><tr><th></th><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th><th>G</th><th>H</th></tr></thead><tbody><tr><td rowspan="2">1</td><td>aaa</td><td>abe</td><td>eca</td><td>ede</td><td>bec</td><td>bfg</td><td>fgc</td><td>fhg</td></tr><tr><td>bec</td><td>bfg</td><td>fgc</td><td>fhg</td><td>aaa</td><td>abe</td><td>eca</td><td>ede</td></tr><tr><td rowspan="2">2</td><td>aab</td><td>abf</td><td>ecb</td><td>edf</td><td>bed</td><td>bfh</td><td>fgd</td><td>fhh</td></tr><tr><td>bed</td><td>bfh</td><td>fgd</td><td>fhh</td><td>aab</td><td>abf</td><td>ecb</td><td>edf</td></tr><tr><td rowspan="2">3</td><td>caa</td><td>cbe</td><td>gca</td><td>gde</td><td>dec</td><td>dfg</td><td>hgc</td><td>hhg</td></tr><tr><td>dec</td><td>dfg</td><td>hgc</td><td>hhg</td><td>caa</td><td>cbe</td><td>gca</td><td>gde</td></tr><tr><td rowspan="2">4</td><td>cab</td><td>cbf</td><td>gcb</td><td>gdf</td><td>ded</td><td>dfh</td><td>hgd</td><td>hhh</td></tr><tr><td>ded</td><td>dfh</td><td>hgd</td><td>hhh</td><td>cab</td><td>cbf</td><td>gcb</td><td>gdf</td></tr></tbody></table>

On peut remarquer que dans les images T, lorsqu'une cellule active est mise à jour, il y a trois cellules qui changent d'étiquette : la cellule mise à jour, mais aussi ses voisines de droite et de gauche (cf. fig. 1.4). Si l'on veut avoir une vue de toutes les possibilités de transformation qui ont lieu dans les images T lors d'une mise à jour unique, nous devons donc prendre en compte toutes les mises à jour possibles de triplets d'étiquettes, ce qui correspond à 5 états binaires, donc 32 possibilités.

Ces transitions sont représentées sur la table 1.5, le tableau de réécriture. Les triplets correspondent aux séquences $(\alpha, x, y, z, \beta) \in \{0, 1\}^5$ ainsi présentées : chaque colonne correspond à une valeur fixée $(x, y, z)$, et les quatre colonnes correspondent aux valeurs des bords $(\alpha, \beta)$ selon l'ordre $(0, 0), (0, 1), (1, 0)$ et $(1, 1)$.

Notons que pour une règle donnée, les seules colonnes à prendre en compte sont celles qui correspondent aux transitions actives.

### 1.2.4 Fonctions potentiels

Il sera fréquemment fait usage de fonctions qui vont de l'ensemble des configurations $\mathcal{E}_n$ à l'ensemble des entiers $\mathbb{N} = \{0, 1, 2, \dots\}$. Nous utiliserons le terme de potentiel pour qualifier ces
fonctions, en effet, par analogie avec ce qui se pratique en physique, elles seront utilisées pour estimer la distance à l'ensemble des points fixes.

On appelle étiquette (en anglais label) les lettres d'une image T d'une configuration donnée.

**Définition 1.** Un potentiel $W : \mathcal{E}_n \to \mathbb{N}$ est p-linéaire s'il se définit comme une combinaison linéaire du nombre d'étiquettes d'une configuration et que tous les coefficients de la combinaison sont positifs.
Formellement : $W(x) = \omega_a \cdot a(x) + \dots + \omega_h \cdot h(x)$ avec $\omega_a, \dots, \omega_h \in \mathbb{N}$.

Nous introduisons quelques définitions pour la suite.

**Définition 2.** On dira que $W$ est équilibré si pour toute configuration, la différence de potentiel produite par une mise à jour d'une cellule ne dépend que de l'étiquette de cette cellule.

On remarquera que comme la mise à jour d'une cellule modifie trois étiquettes, la différence de potentiel dépend en général des trois étiquettes de départ et d'arrivée; le cas équilibré est donc un cas particulier et le lemme suivant précise ses conditions d'obtention.

**Lemme 1** ([78, 87]). Si $W$ est un potentiel p-linéaire tel que : $\omega_a + \omega_d = \omega_b + \omega_c$ et $\omega_e + \omega_h = \omega_f + \omega_g$, alors $W$ est équilibré.

Quand un potentiel est équilibré, nous noterons $\delta_t$ la décroissance de potentiel produite par la mise à jour d'une cellule portant l'étiquette $\vdash$ (dans l'image T).

Pour rappel, $F(x)$ dénote la variable aléatoire qui représente l'évolution du système à partir d'une configuration $x$. Nous notons $\Delta W(x) = W(F(x)) - W(x)$ qui représente la variation de potentiel à partir de $x$ et $E\Delta W(x)$ l'espérance de cette variation de potentiel à partir de $x$. Par exemple, si $x$ a une unique cellule active dont la mise à jour produit une variation de potentiel de $-3$, on a $E\Delta W(x) = -3/n$ car la probabilité que cette cellule soit mise jour est $1/n$. Dans la suite, nous écrirons plus volontiers $n \cdot E\Delta W(x) = -3$ de façon à ne manipuler que des entiers.

Commençons par établir un fait simple qui nous sera utile plus tard : si une règle a un potentiel p-linéaire qui peut toujours décroître jusqu'à atteindre une valeur nulle qui correspond à un point fixe, alors le temps d'atteinte de ce point fixe est presque sûrement fini<fnref n="4" />.

Formellement, en notant $(x^t)$ le processus qui modélise l'évolution du système à partir d'une configuration $x$; nous avons :

**Lemme 2.** Si une règle $f$ est telle qu'il existe un potentiel p-linéaire $W$ tel que pour toute taille d'anneau $n$, il existe $\epsilon > 0$ tel que : $\forall x \in \mathcal{E}_n$

$$ \Pr\{\Delta(x) < 0\} \geq \epsilon, $$

alors pour tout $x \in \mathcal{E}_n$, la variable aléatoire $T(x) = \min\{t \in \mathbb{N} : W(x^t) = 0\}$ est presque sûrement finie.

## 1.3 Règles à convergence logarithmique

Nous commençons notre exposé de la classification par les règles à convergence logarithmique, c'est-à-dire celles pour lesquelles le temps de convergence s'écrit $\tau(n) = \Theta(\log n)$. On trouve dans cette classe pas moins de 27 règles minimales dont l'observation expérimentale

<footnote n="4">4. Nous utilisons l'expression « presque sûrement » au sens de la théorie de la mesure, c'est-à-dire qu'il existe un certain nombre de cas où la convergence n'a pas lieu, mais ces cas sont de mesure nulle dans l'espace des mises à jour possibles.</footnote>
<table><caption>TABLE 1.6 – Liste des règles candidates pour une convergence logarithmique, divisées selon les classes RCH et RCN.</caption><tbody><tr><td rowspan="4">RCH</td><td>0-EFGH</td><td>2-BEFGH</td><td>8-EGH</td><td>10-BEGH</td></tr><tr><td>18-BCEFGH</td><td>24-CEGH</td><td>26-BCEGH</td><td>32-DEFGH</td></tr><tr><td>34-BDEFGH</td><td>40-DEGH</td><td>42-BDEGH</td><td>50-BCDEFGH</td></tr><tr><td>56-CDEGH</td><td>58-BCDEGH</td><td>106-BDEH</td><td></td></tr><tr><td rowspan="3">RCN</td><td>4-FGH</td><td>5-AFGH</td><td>12-GH</td><td>13-AGH</td></tr><tr><td>36-DFGH</td><td>44-DGH</td><td>72-EH</td><td>76-H</td></tr><tr><td>77-AH</td><td>104-DEH</td><td>200-E</td><td>232-DE</td></tr></tbody></table>

laisse penser qu'elles sont à convergence logarithmique; leur liste est présentée dans le tableau 1.6, selon qu'elles convergent rapidement vers un point fixe homogène (RCH) ou non-homogène (RCN).

Les diagrammes espace-temps de ces règles, ainsi que leurs propriétés de « mécanique élémentaire » sont présentés dans les tables 1.1 et 1.2. On constate que toutes ces règles ont en commun la présence d'un *processus de fragmentation* : les régions de 1 ont tendance à se briser en plus petits morceaux, qui vont progressivement disparaître. Essayons maintenant de rendre cette intuition plus formelle.

## Borne inférieure et borne supérieure

**Lemme 3.** La règle d'identité mise à part, la convergence de tous les automates cellulaires est au moins logarithmique.

Ceci vient du simple fait que si une règle possède au moins une transition active, on peut construire une configuration où cette transition est présente dans une cellule sur trois. Il faut donc au moins que ces cellules actives soient mises à jour et soient rendues inactives pour que le système atteigne un point fixe. On montre par un argument de type collectionneur de vignettes (*coupon collector*) que ce temps est logarithmique en $n/3$, donc également logarithmique en $n$.

Pour la borne supérieure, nous utilisons le lemme suivant.

**Lemme 4.** Si pour une règle f différente de l'identité, il existe un entier $m$ et un potentiel $p$-linéaire $W$ tel que pour toute taille d'anneau $n \in \mathbb{N}$ :

$$ (a) \qquad W(x) = 0 \implies x \in \mathbb{F}_p, \text{ et} $$

$$ (b) \qquad \forall x \notin \mathbb{F}_p, n \cdot E\Delta W(x) \leq -\frac{W(x)}{m}, $$

alors f a un temps de convergence logarithmique : $\tau(n) \in \Theta(\log(n))$.

La démonstration de ce lemme est assez technique; elle a été effectuée dans notre article de tutoriel [87] de 2020, ce qui nous a permis d'unifier les techniques de preuves. L'idée intuitive du lemme est que si la baisse de potentiel est proportionnelle au potentiel, alors la convergence se fait en temps logarithmique.

## Règles avec une activité strictement décroissante

On dit qu'une règle a une activité strictement décroissante si le nombre de cellules actives décroît à chaque fois qu'une cellule active est mise à jour. On peut par exemple prendre l'ACE
76-H. Cette règle a une unique transition active et seules les cellules h sont actives. Par ailleurs, les h sont transformés en d et les h ne peuvent jamais apparaître par mise à jour d'une cellule.

**Théorème 1.** *Les règles 0-EFGH, 4-FGH, 12-GH, 76-H, 77-AH, 200-E, et 232-DE ont une activité stric-tement décroissante et ont une convergence logarithmique.*

Il est facile de montrer que ces règles sont logarithmiques puisque leur potentiel est simplement défini comme le nombre de cellules actives.

## Règles avec un potentiel monotone

Dans certains cas compter le nombre de cellules actives ne suffit pas. Prenons l'exemple de la règle EH. Si l'on regarde le table de réécriture des transitions E et H (voir table 1.5), on voit que le nombre de cellules actives décroît toujours sauf dans le cas où un h produit deux e. Nous pouvons donc compter un h comme trois e pour que l'on continue à observer une décroissance de potentiel.

On généralise cette idée comme suit. On dit que $f$ a un potentiel monotone $W$ si $\forall x \in E_n, \forall i \in A(x) \subseteq \mathcal{L}, W(F(x, i)) - W(x) < 0$, où $A(x)$ représente l'ensemble des cellules actives de $x$.

**Théorème 2.** *Les ACE 5-AFGH, 8-EGH, 13-AGH, 72-EH ont un potentiel monotone; leur convergence est logarithmique.*

Pour l'ACE 8-EGH, on prendra $W = e + 2g + h$. C'est un potentiel équilibré pour lequel on a : $\delta_E = \delta_G = \delta_H = -1$. De même, pour l'ACE 72-EH on prend $W = e + 3h$.

Pour les ACE 5-AFGH et 15-ABGH, on prend $W = a + f + g + 2h = a + 2g + 2h$. Ce potentiel n'est pas équilibré mais les conditions d'application du lemme sont vérifiées.

## Règles avec un potentiel décroissant en moyenne

Nous terminons l'examen des règles logarithmique avec le cas où la décroissance n'est garantie qu'en moyenne.

**Théorème 3.** *La convergence des ACE 2-BEFGH, 32-DEFGH, 34-BDEFGH, 40-DEGH est logarithmique.*

Pour ces quatre règles, on prendra $W = 3e + 5f + 2h$. Pour montrer que ce potentiel permet l'application du lemme, on utilise le tableau de réécriture (cf. § 1.2.3 p. 1.2.3) et les équivalences des équations 1.2.

## Règles restantes

**Conjecture 1.** *Les ACE 10-BEGH, 18-BCEFGH, 24-CEGH, 26-BCEGH, 36-DFGH, 42-BDEGH, 44-DGH, 50-BCDEFGH, 56-CDEGH, 58-BCDEGH, 104-DEH, et 106-BDEH ont une convergence logarithmique.*

Nous pensons qu'il n'est pas possible de définir des potentiels p-linéaires pour étudier ces règles. Une solution serait d'utiliser des potentiels définis avec des sous-mots de longueur supérieure à trois. On pourra se reporter au travail de Regnault sur la quantification des transitions de phase pour de l'utilisation de telles techniques [203]. Il est quelque peu surprenant qu'en dépit du fait que nous ayons toujours des *processus de fragmentation* en jeu, nous ne disposions pas d'outils analytiques suffisamment généraux pour pouvoir s'appliquer aux règles citées ci-dessus. Un travail avait été entrepris en collaboration avec Lucas Gerin (École polytechnique) mais sans conduire à des résultats suffisamment aboutis pour être publiés.
<table><caption>TABLE 1.7 – Liste des treize règles démontrées ou conjecturées linéaires selon le PTCM.</caption><thead><tr><th>diag.</th><th>diag.</th><th>Wcode</th><th>Tcode</th><th>01</th><th>10</th><th>101</th><th>010</th><th>conv.</th></tr></thead><tbody><tr><td></td><td></td><td>128</td><td>EFG</td><td>→</td><td>←</td><td>]0[</td><td>*1*</td><td>LIN</td></tr><tr><td></td><td></td><td>130</td><td>BEFG</td><td>↔</td><td>←</td><td>]0[</td><td>*1*</td><td>LIN</td></tr><tr><td></td><td></td><td>132</td><td>FG</td><td>→</td><td>←</td><td>]0[</td><td>]1[</td><td>LIN</td></tr><tr><td></td><td></td><td>136</td><td>EG</td><td>.</td><td>←</td><td>]0[</td><td>*1*</td><td>LIN</td></tr><tr><td></td><td></td><td>140</td><td>G</td><td>.</td><td>←</td><td>]0[</td><td>]1[</td><td>LIN</td></tr><tr><td></td><td></td><td>160</td><td>DEFG</td><td>→</td><td>←</td><td>*0*</td><td>*1*</td><td>LIN</td></tr><tr><td></td><td></td><td>162</td><td>BDEFG</td><td>↔</td><td>←</td><td>*0*</td><td>*1*</td><td>LIN</td></tr><tr><td></td><td></td><td>164</td><td>DFG</td><td>→</td><td>←</td><td>*0*</td><td>]1[</td><td>LIN</td></tr><tr><td></td><td></td><td>168</td><td>DEG</td><td>.</td><td>←</td><td>*0*</td><td>*1*</td><td>LIN</td></tr><tr><td></td><td></td><td>172</td><td>DG</td><td>.</td><td>←</td><td>*0*</td><td>]1[</td><td>LIN</td></tr><tr><td></td><td></td><td>74</td><td>BEH</td><td>←</td><td>.</td><td>]0[</td><td>*1*</td><td>LIN?</td></tr><tr><td></td><td></td><td>78</td><td>BH</td><td>←</td><td>.</td><td>]0[</td><td>]1[</td><td>LIN</td></tr><tr><td></td><td></td><td>94</td><td>BCH</td><td>←</td><td>→</td><td>]0[</td><td>]1[</td><td>LIN</td></tr></tbody></table>
1.4 Règles à convergence linéaire

Les lecteurs peuvent se faire une idée des comportements qui conduisent à une convergence
linéaire en regardant les règles marquées LIN dans le tableau 1.7 (p. 22).

Ce type convergence correspond à l'idée intuitive que l'on a de la façon dont un système est attiré vers son point fixe : « la distance » maximale qu'il a à parcourir pour se stabiliser est proportionnelle à sa taille. Cependant, comme nous allons le voir, ce comportement ne concerne que 13 règles sur 88 et parmi celles-ci, il y a des cas qui sont loin d'être simples.

Le lemme suivant formalise l'idée qu'en dépit de la mise à jour aléatoire du système, il existe un potentiel qui décroît régulièrement en moyenne.

**Lemme 5.** Si une règle f admet un potentiel p-linéaire W tel que pour n suffisamment grand :

(a) $\forall x \in \mathcal{E}_n, W(x) = 0 \implies x \in \mathcal{F} \text{ et}$

(b) $\forall x \notin \mathcal{F} \text{, } n \cdot E\Delta W(x) \le -1,$

alors la convergence de f est au plus linéaire, c'est-à-dire : $\tau(n) \in \mathcal{O}(n)$.

Idée de la démonstration : On considère le processus $Y_t = X_t + \varepsilon t$ avec $\varepsilon = 1/n$ et l'on montre que c'est une surmartingale, c'est-à-dire un processus stochastique dont la valeur moyenne a tendance à décroître au fil du temps.

**Théorème 4 (convergence linéaire).** *Les règles 128-EFG, 130-BEFG, 132-FG, 136-EG, 140-G, 160-DEFG, 162-BDEFG, 164-DFG, 168-DEG, 172-DG ont une convergence linéaire : $\tau(n) = \Theta(n)$.*

*Démonstration.* Nous procéderons en deux temps : nous montrerons d'abord qu'il existe pour chaque règle ci-dessus un potentiel p-linéaire qui vérifie les conditions du lemme 5 ; ceci nous donne une borne supérieure sur le temps de convergence. Dans un second temps, nous exhibitionnerons une borne inférieure sur $\tau(n)$ en calculant le temps de convergence d'une configuration particulière.

**Bornes supérieures.** Pour les règles 128-EFG, 132-FG, 136-EG et 140-G, on peut prendre le nombre de 1 comme potentiel : $W(x) = |x|_1 = e + f + g + h$. En effet pour chaque mise à jour d'une cellule active, un 1 est supprimé et, d'autre part, on ne peut pas créer de 1 : $x \notin \mathcal{F} \implies n \cdot E\Delta W(x) \le -1$.

Si l'on considère les quatre règles 160-DEFG, 164-DFG, 168-DEG et 172-DG, on constate que le nombre de 1 décroît aussi, sauf quand une transition D est mise à jour. Un d ne peut être créé car A, B, C et H sont passives (voir Tab. 1.5). On prendra $W(x) = 2d(x) + |x|_1 = 2d+e+f+g+h$. En effet, quand une cellule à l'état 0 est mise à jour (un d), $|x|_1$ augmente de 1 mais $2d(x)$ décroît de 2, ce qui produit un bilan négatif.

Le cas des règles 130-BEFG et 162-BDEFG est légèrement plus complexe, en effet, les frontières 01 suivent une marche aléatoire non biaisée. En analysant les lois de « mécanique élémentaire » décrites plus haut (cf. Sec. 1.2.1), on trouve la fonction de potentiel : $W(x) = |x|_1 + |x|_{01} = b+d+e+f+g+h$.

Nous laissons aux lecteurs le soin de la vérification de la condition (b) du lemme.

**Bornes inférieures.** Considérons la condition initiale $x = 001^{n-2}$. On peut noter que toutes les configurations évoluant à partir de $x$ sont des configurations à deux régions ou des configurations homogènes, c'est-à-dire que pour tout $t$, $x^t$ est équivalent par décalage à $1^i 0^{n-i}$ avec $i \in \{1, \dots, n-1\}$.
<figure><img src="image_9.png" /><figcaption>FIGURE 1.6 – Chaîne de Markov qui décrit l'évolution de la règle 128-EFG à partir d'une configuration $1^i 0^{n-i}$. L'étiquette de l'état de la chaîne de Markov correspond à $i$ (nombre de 1).</figcaption></figure>

Examinons les règles 128-EFG et 132-FG, 136-EG, 140-G et les quatre autres règles 160-DEFG, 164-DFG, 168-DEG, 172-DG. L'évolution de ces règles est monotone : le nombre de 1 ne peut que décroître. À chaque pas de temps, la probabilité de faire décroître le nombre de 1 est donc $1/n$ ou $2/n$, ce qui correspond à un temps d'attente de $n$ or $n/2$ en moyenne. En sommant $n-2$ opérations de cette sorte, on obtient donc un nombre de pas qui varie quadratiquement en $n$, donc un temps de convergence rééchelonné linéaire en $n$. Une telle évolution est bien représentée par une chaîne de Markov : la figure 1.6 traite le cas de la règle 128-EFG.

Pour la règle 130-BEFG, on note que $1 = 1^\zeta$ n'est pas atteignable. La règle converge sur $0$, et plus lentement que la règle 128-EFG puisque B augmente le nombre de 1.

Pour la règle 162-BDEFG, les choses deviennent plus délicates : le point fixe 1 est désormais atteignable puisque D est active. Néanmoins, les simulations montrent que le système est attiré vers 0. On peut calculer exactement le temps de convergence du système à l'aide de la méthode du pas en avant (cf. ref. [97]). En notant $T_i$ le temps moyen de convergence à un point fixe à partir de $1^i 0^{n-i}$, il vient : $T_0 = 0, T_n = 0$ et, en prenant $\epsilon = 1/n$, on obtient :

$$ \begin{array}{l} T_1 = 1 + \epsilon \cdot T_0 + (1 - 2\epsilon)T_1 + \epsilon \cdot T_2 \\ \forall i \in \{1, \dots, n-1\}, \quad T_i = 1 + 2\epsilon \cdot T_{i-1} + (1 - 3\epsilon)T_i + \epsilon \cdot T_{i+1} \end{array} $$

La solution de ce système a la forme $\frac{1}{\epsilon}\kappa(n)$, où $\kappa(n)$ a un terme linéaire en $n$ et un terme qui décroît exponentiellement en $n$. Ceci nous donne bien un temps de convergence quadratique en $n$, c'est-à-dire un temps rééchelonné qui varie linéairement en $n$. On remarquera que ce système est très proche du problème de la ruine d'un joueur (Gambler's ruin problem) avec une pièce non équilibrée. $\square$

**Théorème 5.** Les règles 78-BH et 94-BCH ont un temps de convergence linéaire.

Pour ces deux règles, on prendra $W = 2a + b + c + h = 2a + 2b + h$. La forme de ce potentiel reflète le fait que les 0-régions ont une tendance à être « grignotées » (voir fig. 1.7).

**Conjecture 2.** La règle 74-BEH a un temps de convergence qui est linéaire.

Le comportement de cette règle est assez intrigant. Sur les simulations, on observe à partir de conditions initiales aléatoires que la règle a une tendance à converger très rapidement (en temps logarithmique). Cependant, il est possible de construire des conditions initiales pour lesquelles la convergence semble se faire en temps linéaire (ou plus). Par exemple, pour $k > 0$, les conditions initiales de type $001(011)^k$ génèrent des cascades qui se propagent de gauche à droite et font progressivement converger le système vers $0 = 0^\zeta$ (voir fig. 1.7). Déterminer la convergence de cette règle est un problème ouvert.
<figure><img src="image_10.png" /><figcaption>FIGURE 1.7 – Diagrammes espace-temps pour $n = 33$. (gauche) : règle 74-BEH avec condition initiale $000(011)^{10}$. (droite) : règle 78-BH avec condition initiale $(0^{27})1(0^5)$. Le temps va du bas vers le haut ; les états 0 et 1 sont représentés par les couleurs blanc et bleu, respectivement. Le temps est rééchelonné d'un facteur $1/n$: un pas de temps (une ligne) correspond à $n$ mises à jour indépendantes. Cette convention est gardée dans la suite document.</figcaption></figure>

<table><caption>TABLE 1.8 – Liste de six règles démontrées quadratiques selon le PTCM.</caption><thead><tr><th>diag.</th><th>diag.</th><th>Wcode</th><th>Tcode</th><th>01</th><th>10</th><th>101</th><th>010</th><th>conv.</th></tr></thead><tbody><tr><td></td><td></td><td>138</td><td>BEG</td><td>←</td><td>←</td><td>]0[</td><td>*1*</td><td>QUAD</td></tr><tr><td></td><td></td><td>146</td><td>BCEFG</td><td>↔</td><td>↔</td><td>]0[</td><td>*1*</td><td>QUAD</td></tr><tr><td></td><td></td><td>152</td><td>CEG</td><td>.</td><td>↔</td><td>]0[</td><td>*1*</td><td>QUAD</td></tr><tr><td></td><td></td><td>170</td><td>BDEG</td><td>←</td><td>←</td><td>*0*</td><td>*1*</td><td>QUAD</td></tr><tr><td></td><td></td><td>178</td><td>BCDEFG</td><td>↔</td><td>↔</td><td>*0*</td><td>*1*</td><td>QUAD</td></tr><tr><td></td><td></td><td>184</td><td>CDEG</td><td>.</td><td>↔</td><td>*0*</td><td>*1*</td><td>QUAD</td></tr></tbody></table>
## 1.5 Règles à convergence quadratique

Par souci de concision, on ne donnera pas ici le lemme qui permet d'obtenir le résultat sur le temps quadratique. En effet, nous présenterons au paragraphe 7.3 (page 88) un lemme similaire.

**Théorème 6.** Les règles 170-BDEG, 178-BCDEFG et 184-CDEG ont un temps de convergence quadratique.

La démonstration repose sur la construction d'une martingale qui consiste à compter le nombre 1, quantité que l'on corrige plus ou moins selon les cas spéciaux que sont les 0 ou 1 isolés [97].

On remarque que les trois règles citées sont bien connues : la règle 170-BDEG correspond au décalage à gauche (shift), la règle 178 à la règle « bascule-si-non-égalité » (FLIP-IF-NOT-EQUAL), étudiée notamment par Regnault pour le cas de l'α-synchronisme [201]; la règle 184 est la règle de circulation (traffic). Cette dernière règle sera notamment utilisée dans le chapitre 7 (p. 85).

**Théorème 7 ([97]).** Les règles 138-BEG, 146-BCEFG, 152-CEG ont un temps de convergence quadratique.

Ce comportement est plus surprenant. En effet, pour ces trois règles, bien que la tendance générale soit à conserver le nombre de 1, on ne peut converger que vers le point fixe 0. Ceci peut facilement se comprendre en analysant le code par transitions : la transition D est passive, ce qui rend la disparition du dernier 0 impossible. Il se produit donc un phénomène de « rebond » de la marche aléatoire. Pour obtenir une convergence en temps quadratique, on utilise une technique bien connue : on effectue un couplage entre le processus qui évolue entre 0 et $n-1$ (qui rebondit sur $n$) et une marche aléatoire « classique » entre 0 et $2n$.

<table><caption>TABLE 1.9 – Liste de trois règles démontrées ou conjecturées exponentielles selon le PTCM.</caption><thead><tr><th>diag.</th><th>diag.</th><th>Wcode</th><th>Tcode</th><th>01</th><th>10</th><th>101</th><th>010</th><th>conv.</th></tr></thead><tbody><tr><td></td><td></td><td>154</td><td>BCEG</td><td>←</td><td>↔</td><td>]0[</td><td>*1*</td><td>EXP</td></tr><tr><td></td><td></td><td>90</td><td>BCEH</td><td>←</td><td>→</td><td>]0[</td><td>*1*</td><td>EXP?</td></tr><tr><td></td><td></td><td>122</td><td>BCDEH</td><td>←</td><td>→</td><td>*0*</td><td>*1*</td><td>EXP?</td></tr></tbody></table>

## 1.6 Règles à convergence exponentielle

**Théorème 8.** La règle 154-BCEG a un temps de convergence exponentiel.

La figure 1.8 montre l'évolution de cette règle. Là aussi, le fait que la transition D soit passive rend le point fixe 1 inatteignable et produit de nouveau un phénomène de rebond. La démonstration de la convergence exponentielle se fait en deux temps : on calcule d'abord le temps mis
<figure><img src="image_11.png" /></figure>

FIGURE 1.8 – Espace-temps d’une évolution de la règle 154-BCEG avec une condition initiale aléatoire.

par les configurations à deux zones. Ceci se fait par la résolution du système suivant :

$$
\begin{align*}
T_0 &= 0 \\
T_i &= 1 + \varepsilon T_{i-1} + (1-3\varepsilon)T_i + 2\varepsilon T_{i+1} \quad \text{pour } i \in \{1, \dots, n-2\} \\
T_{n-1} &= 1 + \varepsilon T_{n-2} + (1-\varepsilon)T_{n-1}.
\end{align*}
$$

où $T_i$ est le temps d'atteinte du point fixe 0 à partir d'une configuration $1^i 0 n - i$.

Dans un second temps, on procède à un couplage pour montrer qu'une convergence d'une
configuration à plusieurs zones $x$ est plus rapide que la convergence d'une configuration à deux
zones particulière $y$. Pour cela, on marque une zone de 0 arbitraire dans la configuration de
départ $x$, on construit $y$ en mettant les mêmes cellules à l'état 0 et toutes les autres cellules à
l'état 1. On fait évoluer les deux processus en mettant à jour les mêmes cellules et en décalant
$y$ de manière à ce que la frontière 01 marquée dans $x$ et celle de $y$ coïncident. Le système
étant invariant par décalage, l'ajout de cette étape supplémentaire ne perturbe pas les temps de
convergence des processus. On montre que si $y$ converge, alors $x$ converge. On a donc majoré
le cas général par un cas à deux zones, que l'on sait traiter. La mécanique de la démonstration
reste donc assez complexe et il serait intéressant de chercher à la simplifier.

**Conjecture 3.** *Les règles 90-BCEH et 122-BCDEH ont un temps de convergence exponentiel.*

On peut noter que pour ces deux règles, 0 est un point fixe pour tout n et pour n = 3k, la
configuration $x_F = (101)^k \stackrel{t}{=} (gdf)^k$ est également un point fixe.

Pour démontrer que la convergence est au moins exponentielle, on pourrait montrer que
0 est atteignable à partir de toute configuration qui n'est pas un point fixe. Dans un second
temps, on chercherait à établir une borne supérieure pour le temps d'absorption vers 0.

C'est un problème ouvert que d'établir un lemme qui unifierait les approches et donnerait
un outil général d'analyse de la convergence exponentielle d'une règle. Ces règles sont dans un
état métastable : elles passent un temps très long dans un espace d'états qui est loin de l'énergie
minimale puis une combinaison peu probable de mises à jour conduit le système à atteindre
un point fixe (les diagrammes espace-temps de la table 1.9 peuvent difficilement montrer cela).
On pourra par exemple se référer à la synthèse de Cirillo et al. pour en savoir plus sur les
phénomènes de métastabilité [48]
<figure><img src="image_12.png" /><figcaption>FIGURE 1.9 – Représentation de la chaîne de Markov qui décrit l'évolution de la règle 154-BCEG à partir de la configuration $1^i 0^{n-i}$. L'état de la chaîne de Markov correspond au nombre de 1.</figcaption></figure>

<table><caption>TABLE 1.10 – Liste de règles démontrées non convergentes (19 premières).</caption><thead><tr><th>diag.</th><th>diag.</th><th>Wcode</th><th>Tcode</th><th>01</th><th>10</th><th>101</th><th>010</th><th>conv.</th></tr></thead><tbody><tr><td></td><td></td><td>1</td><td>AEFGH</td><td>→</td><td>←</td><td>]0[</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>3</td><td>ABEFGH</td><td>↔</td><td>←</td><td>]0[</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>6</td><td>BFGH</td><td>↔</td><td>←</td><td>]0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>7</td><td>ABFGH</td><td>↔</td><td>←</td><td>]0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>9</td><td>AEGH</td><td>.</td><td>←</td><td>]0[</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>11</td><td>ABEGH</td><td>←</td><td>←</td><td>]0[</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>14</td><td>BGH</td><td>←</td><td>←</td><td>]0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>15</td><td>ABGH</td><td>←</td><td>←</td><td>]0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>19</td><td>ABCEFGH</td><td>↔</td><td>↔</td><td>]0[</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>22</td><td>BCFGH</td><td>↔</td><td>↔</td><td>]0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>23</td><td>ABCFGH</td><td>↔</td><td>↔</td><td>]0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>25</td><td>ACEGH</td><td>.</td><td>↔</td><td>]0[</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>27</td><td>ABCEGH</td><td>←</td><td>↔</td><td>]0[</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>28</td><td>CGH</td><td>.</td><td>↔</td><td>]0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>29</td><td>ACGH</td><td>.</td><td>↔</td><td>]0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>30</td><td>BCGH</td><td>←</td><td>↔</td><td>]0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>33</td><td>ADEFGH</td><td>→</td><td>←</td><td>*0*</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>35</td><td>ABDEFGH</td><td>↔</td><td>←</td><td>*0*</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>37</td><td>ADFGH</td><td>→</td><td>←</td><td>*0*</td><td>]1[</td><td>NCV</td></tr></tbody></table>
<table><caption>TABLE 1.11 – Liste de règles démontrées non convergentes (suite).</caption><thead><tr><th>diag.</th><th>diag.</th><th>Wcode</th><th>Tcode</th><th>01</th><th>10</th><th>101</th><th>010</th><th>conv.</th></tr></thead><tbody><tr><td></td><td></td><td>38</td><td>BDFGH</td><td>↔</td><td>←</td><td>*0*</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>41</td><td>ADEGH</td><td>.</td><td>←</td><td>*0*</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>43</td><td>ABDEGH</td><td>←</td><td>←</td><td>*0*</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>45</td><td>ADGH</td><td>.</td><td>←</td><td>*0*</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>46</td><td>BDGH</td><td>←</td><td>←</td><td>*0*</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>51</td><td>ABCDEFGH</td><td>↔</td><td>↔</td><td>*0*</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>54</td><td>BCDFGH</td><td>↔</td><td>↔</td><td>*0*</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>57</td><td>ACDEGH</td><td>.</td><td>↔</td><td>*0*</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>60</td><td>CDGH</td><td>.</td><td>↔</td><td>*0*</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>62</td><td>BCDGH</td><td>←</td><td>↔</td><td>*0*</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>73</td><td>AEH</td><td>.</td><td>.</td><td>].0[</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>105</td><td>ADEH</td><td>.</td><td>.</td><td>*0*</td><td>*1*</td><td>NCV</td></tr><tr><td></td><td></td><td>108</td><td>DH</td><td>.</td><td>.</td><td>*0*</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>110</td><td>BDH</td><td>←</td><td>.</td><td>*0*</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>126</td><td>BCDH</td><td>←</td><td>→</td><td>*0*</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>134</td><td>BFG</td><td>↔</td><td>←</td><td>].0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>142</td><td>BG</td><td>←</td><td>←</td><td>].0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>150</td><td>BCFG</td><td>↔</td><td>↔</td><td>].0[</td><td>]1[</td><td>NCV</td></tr><tr><td></td><td></td><td>156</td><td>CG</td><td>.</td><td>↔</td><td>].0[</td><td>]1[</td><td>NCV</td></tr></tbody></table>
<table><caption>TABLE 1.12 – Liste des ACE non convergents.</caption><tr><td>1-AEFGH</td><td>3-ABEFGH</td><td>6-BFGH</td><td>7-ABFGH</td><td>9-AEGH</td><td>11-ABEGH</td></tr><tr><td>14-BGH</td><td>15-ABGH</td><td>19-ABCEFGH</td><td>22-BCFGH</td><td>23-ABCFGH</td><td>25-ACEGH</td></tr><tr><td>27-ABCEGH</td><td>28-CGH</td><td>29-ACGH</td><td>30-BCGH</td><td>33-ADEFGH</td><td>35-ABDEFGH</td></tr><tr><td>37-ADFGH</td><td>38-BDFGH</td><td>41-ADEGH</td><td>43-ABDEGH</td><td>45-ADGH</td><td>46-BDGH</td></tr><tr><td>51-ABCDEFGH</td><td>54-BCDFGH</td><td>57-ACDEGH</td><td>60-CDGH</td><td>62-BCDGH</td><td>73-AEH</td></tr><tr><td>105-ADEH</td><td>108-DH</td><td>110-BDH</td><td>126-BCDH</td><td>134-BFG</td><td>142-BG</td></tr><tr><td>150-BCFG</td><td>156-CG</td><td></td><td></td><td></td><td></td></tr></table>

## 1.7 Règles non convergentes

**Théorème 9.** Les 38 règles énumérées dans les tables 1.12 sont non-convergentes.

Il existe plusieurs raisons pour laquelle ces règles sont classées dans la catégorie des « non-convergents ». Nous allons maintenant énumérer ces raisons sans entrer dans les détails des preuves.

La première cause de non-convergence vers un point fixe est qu'une règle... n'admette pas de point fixe !

**Proposition 1.** Les règles suivantes n'admettent pas de point fixe : 1-AEFGH, 3-ABEFGH, 9-AEGH, 11-ABEGH, 19-ABCEFGH, 25-ACEGH, 27-ABCEGH, 33-ADEFGH, 35-ABDEFGH, 41-ADEGH, 43-ABDEGH, 51-ABCDEFGH, 57-ACDEGH.

On se convainc assez facilement de cette proposition en examinant les diagrammes de de Bruijn (cf. § 1.2.2 p. 16).

Une autre raison simple de non-convergence est l'impossibilité à atteindre un point fixe.

**Proposition 2.** Pour les règles suivantes, 0 est un point fixe unique, qui n'est pas atteignable à partir d'autres configurations que lui-même : 38-BDFGH, 46-BDGH, 54-BCDFGH, 60-CDGH, 62-BCDGH, 110-BDH et 126-BCDH.

On peut également avoir des ensembles de configurations qui ne conduisent jamais à une convergence : on dit qu'elles forment un ensemble récurrent (cf. chap. suivant).

**Proposition 3.** Les règles 28-CGH, 29-ACGH, 73-AEH, et 108-DH ont des ensembles récurrents de configurations pour une infinité de valeurs de n.

On observe pour ces règles des phénomènes de « clignotement » : pour certaines configurations, on oscille entre deux ou plusieurs configurations et en revenant toujours à la condition initiale. Ce phénomène sera étudié plus en détail dans le chapitre suivant.

Un autre phénomène apparaît pour certaines règles : la tendance naturelle à produire des bandes où les 0 et les 1 alternent.

**Proposition 4.** Les règles 6-BFGH, 7-ABFGH, 14-BGH, 15-ABGH, 22-BCFGH, 23-ABCFGH, 30-BCGH sont non-convergentes.

Pour ces règles si on examine l'évolution d'une configuration de type $x = 001(01)^k$, on s'aperçoit qu'elle est « frustrée » : étant de taille impaire elle contient nécessairement une paire de cellules adjacentes dans le même état 00 ou 11 ; cette paire ne peut disparaître.

Ce phénomène de bandes se généralise à des alternances d'états de période supérieure à 2 :
**Proposition 5.** Pour $n \in 4\mathbb{N}$, la règle 105-ADEH a un unique point fixe, aux décalages près et pas de point fixe pour $n \notin 4\mathbb{N}$.

Pour $n \in 3\mathbb{N}$, les règles 37-ADFGH et 45-ADGH ont un unique point fixe, aux décalages près, et pas de point fixe pour $n \notin 3\mathbb{N}$.

Pour $n \in 2\mathbb{N}$, les règles 7-ABFGH, 15-ABGH, 23-ABCFGH et 29-ACGH un unique point fixe, aux décalages près, et pas de point fixe pour $n \notin 2\mathbb{N}$.

Nous avons donc réussi à classer, soit de manière analytique, soit de manière empirique, les 88 règles non-équivalentes d'automates cellulaires élémentaires. Si le critère du PTCM ne capture pas tout le comportement asynchrone d'une règle, il permet d'en saisir une caractéristique importante.

Nous achevons donc ce premier chapitre sur la liste de questions suivantes :

**Question 1.** Montrer la convergence logarithmique des ACE 10-BEGH, 18-BCEFGH, 24-CEGH, 26-BCEGH, 36-DFGH, 42-BDEGH, 44-DGH, 56-CDEGH, 58-BCDEGH, 104-DEH, et 106-BDEH en proposant si possible une théorie générale utilisant le fait que des processus de fragmentation sont en jeu.

**Question 2.** Montrer la convergence linéaire de l'ACE 74-BEH.

**Question 3.** Montrer la convergence exponentielle des ACE 90-BCEH et 122-BCDEH.

**Question 4.** Étudier analytiquement ou numériquement comment sont reliées les convergences selon le mode totalement asynchrone et selon le mode $\alpha$-synchrone.
# Récurrence des automates cellulaires élémentaires

Ce chapitre présente les travaux effectués avec nos collaborateurs de l'université du Bengale oriental en Inde. Le premier résultat est paru en 2014 dans les actes de la conférence TAMC [228] et le second résultat a été publié en 2018 dans le *Festschrift* dédié au professeur Kenichi Morita [99]. En se focalisant sur une question précise, ce chapitre permet d'approfondir l'apport des chaînes de Markov dans la compréhension du comportement des automates asynchrones.

La question de la réversibilité des automates cellulaires constitue un champ d'étude important, notamment parce qu'elle lie la question du temps et la question de la conservation de l'information au cours de l'évolution d'un système [139].

En physique, c'est un problème bien connu que de comprendre comment des lois réversibles au niveau local produisent des phénomènes irréversibles au niveau global : c'est le fa-meux « second principe de la thermodynamique ».

Dans le contexte particulier des automates cellulaires, un effort important a été déployé pour comprendre sous quelles conditions une règle locale était réversible. On pourra se référer à l'article d'état de l'art de Morita pour plus de détails [173].

Dans la majorité des cas, on interprète la réversibilité comme un déterminisme rétrograde (*backward determinism*), c'est-à-dire la capacité à revenir de manière unique au temps précédent, étant donné une configuration [10, 208, 240]. Il est à noter que dans le cas des automates finis, et dans ce cas seulement, ceci implique que le système « boucle » en revenant infiniment souvent aux mêmes configurations.

Nous nous demandons maintenant quel est l'équivalent de la propriété de réversibilité quand l'évolution de l'automate cellulaire est soumise à un aléa. Dans nos automates cellulaires asynchrones, l'aléa dans la mise à jour implique que chaque configuration peut avoir plusieurs successeurs, aussi on ne peut plus continuer à utiliser le critère de la bijectivité de la fonction de transition globale (i.e., la mise en correspondance unique d'une configuration et son image). On peut néanmoins garder l'idée d'examiner quels sont les systèmes qui reviennent infiniment souvent à leur condition initiale : de tels systèmes seront dits *récurrents* et, comme leurs analogues déterministes, ils conservent une partie de l'information liée à la condition initiale au cours de leur évolution.
Un équivalent possible de la réversibilité dans le monde des systèmes dynamiques discrets stochastiques est donc la *récurrence*. Plutôt que de chercher des conditions générales d'application, nous proposons maintenant simplement d'examiner l'espace des 256 automates cellulaires élémentaires et d'examiner si nous pouvons les classer en règles récurrentes et non-récurrentes.

## 2.1 Définitions

Soient $x, y \in \mathcal{E}_n$ deux configurations de taille $n$, on dit que $y$ est un successeur de $x$ s'il existe $u \in \mathcal{L}$ tel que $F(x, u) = y$. Pour $x \in \mathcal{E}_n$, on dénote par $\text{succ}(x) = \{F(x, u), u \in \mathcal{L}\}$ l'ensemble des successeurs $x$ et par $\text{succ}(S) = \cup_{x \in S} \text{succ}(x)$ l'ensemble des successeurs de $S \subseteq \mathcal{E}_n$.

La relation *accessible* (ou atteignable) est obtenue comme la clôture transitive la relation *successeur*, c'est-à-dire que de $y$ est accessible à partir de $x$ s'il existe un chemin de configurations qui mène à $y$ en partant de $x$, chaque configuration étant le successeur de la suivante.

**Définition 3.** Une configuration (de taille $n$) $x \in \mathcal{E}_n$ est récurrente si pour toute configuration $y \in \mathcal{E}_n$ qui est accessible de $x$, $x$ est également accessible de $y$. Une configuration qui n'est pas récurrente est transiente.

Lorsque $y$ est accessible de $x$ et $x$ est accessible de $y$, on dit que $x$ et $y$ *communiquent*. Par convention, une configuration communique avec elle-même. La relation *communiquer avec* est une relation d'équivalence; elle permet de découper l'ensemble des configurations en *classes de communication*. On note $\mathcal{C}(n)$ le nombre de classes de communication pour une taille d'anneau $n$.

Deux comportements existent donc : pour les configurations transientes, le système reste un temps fini dans sa classe de communication, puis la quitte définitivement, alors que si le système est initialisé sur une configuration récurrente, il reste éternellement dans la classe de communication de cette configuration.

On dira qu'une règle est récurrente pour la taille $n$ si toutes les configurations de taille $n$ sont récurrentes. Par extension, on appelle *règle récurrente* une règle récurrente pour toute taille.

## 2.2 Conditions de non-récurrence

Une règle est dite *non-récurrente* si elle possède au moins une configuration transiente, c'est-à-dire, pour laquelle le système ne revient pas infiniment souvent.

Pour une règle donnée, nous noterons par $A, B, \dots$, par $\overline{A}, \overline{B}, \dots$ le fait que les transitions A, B, ... sont respectivement actives ou passives.

**Théorème 10 ([228]).** Une règle est non-récurrente si elle vérifie l'une de ces conditions :

- 1a : $\overline{A}E$ ou $1b : \overline{D}H$,

- 2a : $\overline{A}E$ ou $2b : \overline{D}H$,

- 3a : $\overline{A}BCEF$ ou $3b : \overline{A}BCEG$ ou $3c : \overline{B}DFGH$ ou $3d : \overline{C}DFGH$,

- 4a : $\overline{A}BEFG$ ou $4b : \overline{A}CEFG$ ou $4c : \overline{B}CDFH$ ou $4d : \overline{B}CDGH$.

Notons que les conditions énoncées sur la même ligne sont équivalentes par conjugaison ou par réflexion. La preuve du théorème réside simplement dans la possibilité de trouver des contre-exemples à une évolution réversible pour chacun des cas. Par exemple, si l'on considère la règle BCE, celle-ci vérifie la condition (2a) puisque A est active et E est passive. Si nous analysons l'évolution de la configuration $x = 00100$ et mettons à jour la troisième cellule, nous atteignons le point fixe 00000 et nous ne pouvons plus alors revenir à la condition initiale $x$.
Le théorème énoncé ci-dessus concerne 70 règles minimales. Il est à noter que dans cet ensemble, il en existe 46 qui sont fortement irréversibles dans le sens où elles possèdent des configurations pour lesquelles le système ne revient jamais au point de départ.

## 2.3 Récurrence de dix-huit règles

Il nous reste donc 18 règles minimales candidates qui sont potentiellement récurrentes. Le théorème suivant établit que ces règles sont bien récurrentes.

**Théorème 11** ([99]). Les 16 règles suivantes sont récurrentes pour toutes les tailles d'anneau $n$ :

35-ABDEFGH, 38-BDFGH, 43-ABDEGH, 46-BDGH,
51-ABCDEFGH, 54-BCDFGH, 57-ACDEGH, 60-CDGH,
62-BCDGH, 105-ADEH, 108-DH, 134-BFG,
142-BG, 150-BCFG, 156-CG, 204-I.

Les règles 33-ADEFGH et 41-ADEGH sont récurrentes pour $n \neq 3$.

Les démonstrations demandent une analyse fine du comportement des automates cellulaire. Nous invitons les lecteurs à consulter la ref. [99] pour découvrir les techniques d'analyse des espaces de chaînes de Markov. La propriété suivante présente néanmoins un cas où cette analyse est simple.

**Définition 4.** Pour une paire de configurations $x, y \in \mathcal{E}_n$, on dit que $y$ est un successeur de $x$ s'il existe une mise à jour $u \in \mathcal{L}$ telle que $F(x, u) = y$. On dit que $y$ est atteignable à partir de $x$ s'il existe une suite de relations successeur qui mènent de $x$ à $y$.

**Définition 5.** Une règle est directement récurrente si pour toute paire de configurations $x, y \in \mathcal{E}_n$, si $y$ est successeur de $x$, alors $x$ est successeur de $y$.

**Proposition 6.** Les règles suivantes sont directement récurrentes : 51-ABDEFGH, 54-BCDFGH, 57-ACDEGH, 60-CDGH, 105-ADEH, 108-DH, 150-BCFG, 156-CG, 204-I.

En effet, une règle est directement récurrente si et seulement si pour chacune des quatre paires de transitions suivantes : A et E, B et F, C et G, D et H, les deux transitions sont toutes deux actives ou toutes deux passives.

## 2.4 Détermination des classes de récurrence

Pour aller plus loin dans l'analyse de la dynamique, nous cherchons à analyser la structure des ensembles de configurations récurrentes. Notre but est de déterminer le nombre et la « forme » des classes de récurrence des dix-huit règles minimales identifiées.

**Lemme 6.** Étant donné une règle f et une taille d'anneau $n$, soit $(E_i)_{i \in \{1, \dots, k\}}$ une partition de l'espace des configurations $\mathcal{E}_n$ et soit $\{r_i\}$ un ensemble de configurations tel que : $\forall i \in \{1, \dots, k\}$, $r_i \in E_i$. Si, pour tout $i \in \{1, \dots, k\}$ :

(a) toute configuration de $E_i$ communique avec $r_i$,

(b) $E_i$ est clos par l'application de $F$ (i.e., les successeurs des éléments de $E_i$ sont dans $E_i$), alors $f$ est récurrente et ses classes de communication sont formées par les ensembles $(E_i)$.
Chaque configuration $r_i$ est appelée *configuration-représentant* de sa classe de communication. Il va de soi que l'on choisira pour chaque classe une configuration qui facilitera l'application du lemme.

On peut alors utiliser ce lemme pour déterminer le nombre de classes de communication d'une règle donnée. Nous présentons maintenant différents cas, en allant du plus grand nombre de classe au plus petit nombre.

### 2.4.1 Règles avec un nombre de classes de communication exponentiel en $n$

Clairement, l'identité 204-1 a un nombre de classes égal au nombre de configurations, donc égal à $2^n$ et exponentiel en $n$.

**Proposition 7.** La règle 156-CG est récurrente. Le nombre de ses classes de communication $C_{CG}$ varie exponentiellement en $n$. En effet, on a $C_{CG}(n) \sim \phi^n$, où $\phi = (1 + \sqrt{5})/2$ est le nombre d'or.

On montre en effet que le nombre de classes de communication est très proche du nombre de mots binaires qui ne contiennent pas le motif 11. Il est connu que le nombre de tels mots est donné par la suite de Fibonacci, dont le ratio entre un nombre et son successeur tend vers le nombre d'or. Les premiers éléments de la suite $C_{CG}(n)$ sont 2, 4, 5, 8, 12, 19, 30. Cette suite porte l'indice A001612 dans l'encyclopédie en ligne des suites d'entiers (On-Line Encyclopedia of Integer Sequences, OEIS).

**Proposition 8.** La règle 108-DH est récurrente et le nombre de ses classes de communication $C_{DH}(n)$ croît exponentiellement en $n$. Plus précisément, la suite obéit à la relation récurrence suivante : $C_{DH}(n) = C_{DH}(n-1) + C_{DH}(n-2) + C_{DH}(n-4)$ avec $C(1) = 2$, $C(2) = 2$, $C(1) = 5$, $C(1) = 10$.

Cette suite porte le numéro A259967 dans l'OEIS. Pour trouver l'équivalent de la suite en l'infini, on cherche les racines du polynôme $P(x) = x^4 - x^3 - x^2 - 1 = (x+1)(x^3 - 2x^2 + x - 1)$. On peut vérifier que les quatre racines de $P$ sont $-1, \lambda \approx 1.75488$, et deux solutions complexes dont le module est strictement inférieur à 1. Par conséquent on a : $C_{DH}(n) \sim C.\lambda^n$ où $C$ est une constante qui, de façon inexplicquée, vaut 1.

### 2.4.2 Règles avec un nombre linéaire de classes de communication

**Proposition 9.** Les règles 134-BFG, 142-BG, sont 150-BCFG sont récurrentes. Leurs classes de communications sont formées par leurs points fixes et par les configurations qui ont même nombre de régions de 1.

Le nombre de leurs classes de communication est donné par : $C(n) = \begin{cases} 3 + n/2 & \text{si } n \in 2\mathbb{Z}, \\ 2 + \lfloor n/2 \rfloor & \text{sinon.} \end{cases}$

Pour la règle 142-BG, un exemple illustratif est fourni sur la table 2.1. Il montre comment passer d'une configuration arbitraire à une configuration-représentant et vice versa.

**Proposition 10.** La règle 105-ADEH est récurrente. Le nombre de ses classes de communication $C$ varie selon la taille de l'anneau $n$ selon :

$$C(n) = \begin{cases} 2 & \text{si } n \in 2\mathbb{Z} + 1 \\ n/2 + 3 & \text{if } n \in 4\mathbb{Z} \\ n/2 & \text{sinon.} \end{cases}$$
<figure><img src="image_13.png" /><figcaption>FIGURE 2.1 – Graphe de communication pour la règle 105-ADEH et une taille d’anneau $n = 6$. Les symboles $X$ et $\cdot$ représentent respectivement la présence ou l’absence d’une différence entre l’état d’une cellule et sa voisine de droite. Les liens d’une configuration vers elle-même ne sont pas représentés ; les liens sont bidirectionnels.</figcaption></figure>
<table><caption>TABLE 2.1 – Règle 142-BG: Suite de configurations montrant la communication entre une configuration arbitraire $x$ et une configuration-représentant $s_3$. Les configurations $\alpha, \beta, \gamma$ et $\delta$ sont des étapes intermédiaires.</caption><tbody><tr><td>x</td><td>1100111010111<br>hgcbfhgdedchh</td><td>s<sub>3</sub></td><td>1010100000000<br>edede caaaaaab</td></tr><tr><td>α</td><td>0000100010100<br>aaabecabedeca</td><td>γ</td><td>0000001010100<br>aaaaabededeca</td></tr><tr><td>β</td><td>0000101010000<br>aaabededecaaa</td><td>δ</td><td>0100001010000<br>becaaaabedeca</td></tr><tr><td>s<sub>3</sub></td><td>1010100000000<br>edede caaaaaab</td><td>x</td><td>1100111010111<br>hgcbfhgdedchh</td></tr></tbody></table>

vers une configuration-représentant

à partir d'une configuration-représentant

Nous sommes là en présence de l'une des règles les plus délicates à analyser [99]. Notons que la règle locale s'écrit $f(x, y, z) = 1 \oplus x \oplus y \oplus z$, c'est-à-dire qu'elle donne l'inverse du XOR sur les trois arguments.

L'idée de la démonstration est la suivante. On transforme les configurations en faisant un *ou exclusif* entre une cellule et sa voisine de droite. On montre alors que les paires de 11 (transformées) sont conservées lors de l'évolution du système. C'est cette structure qui explique la dépendance du nombre de classes de communication selon la divisibilité par 4. Un exemple du graphe de communication pour la taille 6 est donné sur la figure 2.1.

### 2.4.3 Règles avec deux classes de communication

**Proposition 11.** *Les cinq règles 38-BDFGH, 46-BDGH, 54-BCDFGH, 60-CDGH, et 62-BCDH sont récurrentes. Leurs classes de communication sont constituées du point fixe 0 et par le reste de l'espace des configurations $\mathcal{E}_n \setminus \{0\}$.*

La démonstration de cette proposition repose sur le fait que la configuration homogène 1 est un « point olympique » : d'une part, ce point peut être atteint à partir de n'importe quelle configuration (montée). D'autre part, on peut atteindre n'importe quelle configuration à partir de ce point en transformant des 1 en 0 (descente).

### 2.4.4 Règle avec une unique classe de communication

**Proposition 12.** *Pour une taille d'anneau $n \neq 3$, les règles 33-ADEFGH et 41-ADEGH sont ergodiques, c'est-à-dire que l'espace des configurations constitue leur unique classe de communication.*

La preuve de la propriété est obtenue en trois étapes : (a) 0 est un « point avernal », c'est-à-dire qu'il peut être atteint à partir de n'importe quelle configuration en transformant des 0 en 1 ; (b) 1 est atteignable à partir de 0 ; (c) 1 est un point olympique.

**Proposition 13.** *Les quatre règles suivantes sont récurrentes : 35-ABDEFGH, 43-ABDEGH, 51-ABCDEEGH, et 57-ACDEGH.*
<figure><img src="image_14.png" /><figcaption>FIGURE 2.2 – Graphe de communication pour la règle 41-ADEGH et une taille d’anneau $n = 5$. Les nombres en rouge montrent la distance au point olympique 1.</figcaption></figure>
La démonstration est plus simple : on montre que 1 peut être atteint à partir de n'importe quelle configuration et que c'est un point olympique. On se rapportera à la figure 2.1 pour un exemple de graphe de communication donné pour la taille 5.

## 2.5 Questions

Ce chapitre nous donc permis de découvrir un autre cas où l'analyse des chaînes de Mar-kov des règles asynchrones était satisfaisante. Les analyses présentées permettent de classer les règles selon un critère de récurrence et même de dénombrer les classes de communication des systèmes obtenus. Nous pensons néanmoins que ce type d'approche reste assez « régional » dans le sens où il est aujourd'hui difficile de faire bien mieux que de considérer les règles une à une. Nous savons par ailleurs que le simple fait de passer du totalement asynchrone à de l'α-synchrone nous fait quitter le domaine de l'analysable, ceci en raison des phénomènes complexes qui entrent alors en jeu, tels que les transitions de phase. Il serait néanmoins judi-cieux de songer à généraliser les différentes techniques autant que possible : jusqu'à quel point pouvons-nous parvenir à englober une large gamme d'automates cellulaires dans notre projet d'étude de l'asynchronisme ? Plus largement, comment ces résultats « régionaux » éclairent-ils la question plus générale de savoir quelles sont les règles robustes aux perturbations et celles qui ne le sont pas, ou partiellement ?

Avant de passer au chapitre suivant et de présenter un panorama plus large du paysage de l'asynchronisme, posons quelques questions plus précises.

**Question 5.** Comment peut-on généraliser la notion de récurrence étudiée ici au cas d'une ligne infinie de cellules ?

Les définitions doivent sans doute être adaptées avec soin de manière à ne pas conduire à des résultats trop triviaux. Par exemple, si l'on exige que la récurrence implique de revenir exactement à la même configuration, on risque de ne plus avoir de règle récurrente du tout...

**Question 6.** Comment la notion étudiée ici s'étend-elle à des classes de règles plus grandes ? En particulier, peut-on décrire une famille infinie de systèmes asynchrones avec une unique classe de communication (donc ergodiques) ?

**Question 7.** Peut-on analyser dénombrer et analyser la forme des classes de communication des règles non-récurrentes ?

Un travail est en cours pour répondre à cette question avec nos collaborateurs indiens Su-kanta Das et Souvik Roy (Indian Institute of Engineering Science and Technology, Shibpur).
# Une cartographie de travaux sur la question de l'asynchronisme

Ce chapitre reprend et développe l'article de l'état de l'art paru dans le *Journal of cellular automata* en 2014 [77]. Bien que ce panorama des articles sur l'asynchronisme des automates cellulaire reste incomplet, différents points ont été revus, notamment à la faveur de l'écriture de notre entrée dans l'encyclopédie des systèmes complexes [85].

Avoir une mise à jour synchrone dans un système comporte de nombreux avantages. Pour les automates cellulaires, les transitions d'état simultanées des cellules permettent d'avoir une définition du modèle simple, où il n'est pas question de s'embarrasser avec un ordre dans la mise à jour et des effets éventuels que cet ordre induit. Il existe néanmoins plusieurs raisons pour lesquelles on souhaite s'intéresser aux automates cellulaires asynchrones :

1. Dans le cadre des systèmes dynamiques, la question est d'évaluer comment les automates cellulaires réagissent aux perturbations de leur mise à jour. Que signifie pour un système dynamique d'être robuste ou sensible à cette perturbation ?

2. Dans le cadre du calcul parallèle, on se demande comment concevoir un dispositif de calcul qui n'utilise pas d'horloge centrale. On s'attend ainsi à des gains en termes de simplicité d'architecture, de consommation énergétique, etc.

3. Dans le cadre de la modélisation, il est nécessaire de s'interroger sur le degré de synchronisme des transitions des cellules. Que représente un pas de temps ? Pourquoi cette échelle de temps et non une autre ? Est-ce réaliste de considérer que toutes les cellules changent d'état en même temps ou qu'une seule cellule seulement change d'état, etc. ?

L'étymologie du terme est claire : α-συν-χρόνος (a-sun-chronos) signifie non-même-temps en grec ancien. La nature *négative* de la définition laisse entendre qu'il n'y a pas une définition unique de l'asynchronisme : on utilisera ce terme dès que l'on s'écartera de la définition standard où toutes les cellules sont mises à jour simultanément.

Rappelons les deux types de mise à jour qui sont utilisées dans notre travail et dans la majeure partie de la littérature scientifique :

— mise à jour **totalement asynchrone** : Une seule cellule est mise à jour à chaque pas de temps de manière aléatoire uniforme.
<figure><img src="image_15.png" /><figcaption>FIGURE 3.1 – Correspondance de la mise à jour en temps continu et discret pour le mode totalement asynchrone.</figcaption></figure>

— mise à jour *α*-synchrone : À chaque pas de temps, chaque cellule est mise à jour avec une probabilité donnée *α*, appelée *taux de synchronisme*.

Comment choisir ? Laquelle de ces deux méthodes est la plus « naturelle » ? Même s'il n'existe évidemment pas de réponse définitive à cette question, on notera que les auteurs ont généralement une préférence pour l'une ou pour l'autre.

Peut-être dira-t-on que la mise à jour totalement asynchrone est la plus « naturelle » si l'on suit le raisonnement suivant : (a) la réalité du temps est continue ; (b) les transitions se produisent à des instants aléatoires ; (c) il y a une probabilité nulle ou négligeable que deux transitions se produisent en même temps ; (d) l'ordre des transitions dans l'espace continu peut être projeté sur un axe de temps discret en prenant la succession des événements de mise à jour (voir la figure 3.1 et par exemple la ref. [224]).

Ces arguments sont pertinents sous l'hypothèse d'avoir des transitions qui soient « instan-
tanées », c'est-à-dire que l'on puisse négliger le temps de passage d'un état à l'autre. Si cette
hypothèse se justifie dans le cadre de la physique, par exemple lorsqu'on modélise des transi-
tions d'état d'atomes ou de molécules, il est en revanche beaucoup plus douteux de la consi-
dérer comme valide par défaut dans le reste des cas. On pense notamment à la biologie, où un
certain degré de synchronisme devrait être supposé. On éviterait ainsi les deux extrêmes du
spectre : la synchronie parfaite est trop régulière pour un phénomène biologique, et l'asynchro-
nisme total est trop exigeant, car il suppose une transmission d'information quasi-instantanée.
Cependant, on voit difficilement comment mesurer un degré de synchronisme sur un système
réel, si bien que l'on préfère en général choisir arbitrairement un mode de mise à jour ou bien
synchrone ou bien totalement asynchrone<fnref n="5" />.

Notons que l’on peut aussi définir des méthodes de mises à jour asynchrones qui ne soient pas aléatoires, par exemple en effectuant la mise à jour des cellules paires puis des cellules impaires (voir p. ex. la ref. [200]). On pourra se référer aux travaux de Schönfisch et de Roos [224], Cornforth et al. [52], Bandini et al. [16] pour des présentations de telles méthodes. Dans la suite du texte, nous nous concentrons de manière exclusive sur les mises à jour asynchrones probabi-listes.

**3.1 Approches expérimentales**

Comme nous l'avons mentionné en introduction, le problème de la classification des au-
tomates cellulaires classiques, c'est-à-dire *synchrones*, suscite encore de nombreuses interro-

<footnote n="5">5. L'idéal serait peut-être que chaque modèle soit observé à la fois en mode totalement asynchrone et en mode α-synchrone pour différentes valeurs du taux de synchronisme α, mais nous sommes bien loin de telles pratiques; la majeure partie des auteurs préfère s'en tenir à un choix déterminé de méthode de mise à jour et ne pas s'embrasser d'un examen de la robustesse de leurs modèles face aux variations de synchronisme.</footnote>
gations (voir p. ex. le travail de Schüle [227, 225] ou celui de Martínez [169]). On pourrait
donc penser que la classification expérimentale ou analytique des automates cellulaires asyn-
chrones est alors bien plus difficile. En fait, il n'en est rien : comme nous le verrons dans ce
chapitre, l'asynchronisme ouvre une nouvelle dimension, laquelle est simplement différente
de la dimension synchrone, et n'est ni plus complexe ni plus simple. L'objet des paragraphes
qui suivent est de clarifier ce point en montrant toute la richesse des approches développées
par différents auteurs au cours des quarante dernières années.

### 3.1.1 Études générales

En 1984, un travail expérimental fondateur a été réalisé par Ingerson et Buvel, qui ont mon-
tré que le comportement de règles simples pouvait être bouleversé par des changements de
mise à jour [37]. C'est dans ce travail qu'apparaît pour la première fois la question de savoir
quelle part attribuer à la règle locale et quelle part attribuer à la mise à jour dans l'observation
d'un comportement donné.

Bersini et Detours reprirent le flambeau quelques années plus tard en explorant la différence entre le Jeu de la vie et quelques variantes asynchrones [22]. Leur contribution principale a été d'observer l'existence d'un « effet stabilisant » de l'asynchronisme. Comme leurs observations se déroulaient sur de petites grilles, ils purent observer que le système pouvait se « geler » sur des points fixes ayant des formes de labyrinthes. Néanmoins, des travaux plus récents ont montré que ce comportement ne pouvait être extrapolé aux tailles de grilles plus grandes [24, 70].

Les travaux de Schönfisch et de Roos furent les premiers à donner des analyses détaillées du comportement des règles asynchrones mais leurs observations restèrent limitées à quelques règles déterminées [224].

**Position de notre travail.** Avec Michel Morvan, nous avons proposé une première étude exhaustive des 256 automates cellulaires élémentaires avec une mise à jour α-asynchrone [96]. Les changements de comportement ont été estimés en calculant une approximation de la densité asymptotique, ce paramètre étant considéré comme un premier moyen de détecter des changements de comportement qualitatifs. Parmi les résultats les plus surprenants de l'étude, nous avons noté l'absence de correspondance entre les classes de robustesse que nous avons définies et les classes de complexité d'automates cellulaires généralement utilisées. C'est-à-dire qu'une règle complexe pouvait devenir simple et, réciproquement, une règle synchrone simple pouvait devenir complexe, comme dans le cas de l'ACE 50 qui génère des transitions de phase avec un changement qualitatif de comportement qui dépend du taux de synchronisme 6.

### 3.1.2 Transitions de phase

Blok et Bergersen ont été les premiers auteurs à identifier le changement qui se produit dans
le jeu de la vie avec une mise à jour α-asynchrone [24]. Ce changement de comportement est
une transition de phase de second ordre, c'est-à-dire que le passage d'une phase à l'autre se
produit de façon continue et en suivant des lois bien définies étudiées en physique statistique.
Plus précisément, les auteurs observent que cette transition de phase appartient à la classe
d'universalité de la percolation dirigée (aussi appelée *percolation orientée*).

**Position de notre travail.** Nous avons identifié des phénomènes similaires dans les automates cellulaires élémentaires et montré que pas moins de *neuf* règles engendraient de telles

<footnote n="6">6. Des observations similaires ont été faites par Bandini et al., en testant sur différentes méthodes de mises à jour et sur des automates cellulaires unidimensionnels avec un voisinage de taille 2 [16].</footnote>
transitions de phase [68]. Nous avons montré qu'au voisinage du seuil critique, la densité suivait une évolution conforme aux lois de puissance prévues pour les phénomènes de percolation dirigée. Une seule règle, l'ACE 178, a été identifié dans une autre classe d'universalité, du fait du rôle symétrique joué par les états 0 et 1.

Nous avons également réexaminé la transition de phase qui se produit dans le jeu de la vie asynchrone, notamment en examinant ce qu'il se produit lorsqu'on introduit des erreurs dans la topologie [69, 70]. Nous avons montré l'existence d'une dépendance forte entre la valeur du seuil critique et la quantité de défauts présents dans la grille.

En ce qui concerne les autres règles bidimensionnelles, citons le travail de Regnault et al. qui ont réalisé un travail pionnier en examinant de près les différents comportements de la règle de minorité en fonction de la topologie choisie et du type d'asynchronisme [202, 204, 214]. Parmi les observations étonnantes, notons que la règle de minorité se stabilisera sur un motif en damier ou sur un motif en bandes selon que la règle s'applique à un voisinage de von Neumann ou à un voisinage de Moore.

Notons que deux points de vue complémentaires peuvent être adoptés sur les transitions de phase : la plupart des auteurs considèrent des systèmes infinis pour lesquels ils montrent qu'un changement qualitatif survient. Regnault a proposé une approche différente en montrant de façon analytique que sur des systèmes de taille finie, la transition correspondait à un changement du temps de convergence vers un point fixe, lequel passait d'une fonction linéaire à une fonction exponentielle en la taille de l'anneau [203].

### 3.1.3 Coalescence

Dans notre étude des ACE asynchrones, nous avons remarqué un phénomène curieux en observant les trajectoires de deux conditions initiales différentes qui sont mises à jour avec la même règle locale et la même suite de mises à jour : dans certains cas une coalescence des trajectoires pouvait avoir lieu rapidement, c'est-à-dire que les deux systèmes atteignent un même état et évoluent ensuite de la même façon (puisqu'ils reçoivent les mêmes mises à jour) [96]. Ce phénomène est facile à expliquer dans bien des cas, notamment quand le système tend rapidement vers un point fixe, mais on peut également l'observer alors que l'automate évolue de façon régulière, par exemple pour l'automate cellulaire élémentaire 46.

De façon imagée, on peut donner l'interprétation suivante : il existe des systèmes asynchrones pour lesquels l'évolution devient rapidement tributaire de la suite des mises à jour et non pas de la condition initiale.

Ce phénomène a formé le cœur du travail de doctorat de Rouquier, qui a étudié de manière très complète ce phénomène pour les 256 ACE [211, 213]. Cette étude a révélé qu'on pouvait observer tout type de comportement vis-à-vis de la coalescence : certaines règles coalescent toujours, d'autres jamais, alors que d'autres coalescent uniquement sur certaines plages du taux d'asynchronisme.

**Position de notre travail.** Expliquer ce phénomène de façon analytique reste une question ouverte. Nous avons exploré cette question lors du stage de Master de Francès de Mas [107] et des pistes intéressantes ont été explorées, sans pour autant déboucher sur une analyse complète du phénomène. Une poursuite de ces recherches reste à faire, peut-être en s'inspirant des résultats obtenus avec d'autres méthodes de couplage [221, 212].
3.1.4 Deux variations de la définition de l'asynchronisme

Alors que la majeure partie des études sur l'asynchronisme ont été consacrées à des types
de mises à jour où les cellules étaient soit mises à jour soit laissées en l'état, nous avons abordé
lors du doctorat d'Olivier Bouré un modèle d'asynchronisme qui prenait en compte des com-
munications imparfaites entre voisins [27, 28, 26]. Ce modèle a été décliné en deux versions,
appelées asynchronisme β et γ, qui considèrent respectivement que des erreurs aléatoires sur-
viennent soit sur l'ensemble du voisinage, soit sur chaque voisin de manière indépendante.

De nombreuses observations ont été effectuées sur ce modèle mais le phénomène le plus
intrigant est sans doute que les transitions de phase observées avec l'asynchronisme de type α
disparaissaient dans certains cas seulement. Plus précisément, les ACE 6, 38 et 134 n'ont plus
de transitions de phase avec les asynchronismes de type β et γ. Le cas de l'ACE 58 est encore
plus troublant puisque il existe une transition de phase pour l'asynchronisme de type α et β
mais pas de type γ ! Ces phénomènes de disparition de transition de phase par passage d'un
modèle d'asynchronisme à l'autre sont un cas assez intéressant de non-robustesse du modèle
et il serait intéressant de regarder ce qui se produit au niveau microscopique pour savoir ce qui
fait qu'une transition de phase peut ainsi disparaître.

Nos observations ont également montré que différentes quantités pouvaient être conser-
vées au cours de l'évolution des systèmes en fonction du modèle d'asynchronisme utilisé. Par
exemple, pour l'ACE 50 il existe des conservations de parité des configurations avec l'asyn-
chronisme de type β qui n'existent pas avec le type α. Ceci souligne la nécessité de poursuivre
le travail d'exploration et d'invention de nouveau type d'asynchronisme afin de mieux com-
prendre à quel point la dynamique des automates cellulaires dépend de leur mode de mise à
jour. Signalons le travail récent de Li et al. qui approfondit cette question de manière significa-
tive [155].

3.1.5 Asynchronisme et bruit

Une autre question concernant l'asynchronisme est de savoir comment cette perturbation
se conjugue avec l'introduction de bruit « classique », c'est-à-dire un changement d'état aléa-
toire des cellules. Gharavi et Anantharam ont été parmi les premiers à examiner ce problème,
et ont approfondi un résultat de Toom, en prenant notamment en compte les délais dans les
communications entre cellules [123]. Le travail de Kanada [138] sur les 256 ACE, et le travail de
Mamei et al. [165] sont également en lien avec cette question.

L'étude de Silva et Correia est une des plus approfondies à ce jour [229]. Dans leur évolution des effets de l'asynchronisme, ces auteurs s'intéressent aux « motifs de différences » (difference patterns), c'est-à-dire aux changements induits par une ou plusieurs modifications de l'état de cellules données. Ils procèdent aussi à une remise à l'échelle du temps en fonction du taux de synchronisme afin d'avoir un nombre moyen de mises à jour moyen par pas de temps qui soit constant.

Le cas des mises à jour asynchrones sur des topologies non régulières a été examiné par Baetens et al., qui ont pris des pavages créés à partir de cellules de Voronoi pour observer l'effet de différentes règles à voisinage de taille variable [14]. Ces auteurs ont analysé les exposants de Lyapunov de différentes règles totalisantes (totalistic) pour évaluer comment la stabilité des règles dépendait de la méthode de mise à jour.
## 3.2 Approches analytiques

Nous nous concentrons maintenant sur les approches analytiques de l'asynchronisme. Il est évident que le découpage approche expérimentale vs. approche analytique est totalement infondé. En effet, nous ne surprendrons personne en affirmant que les études analytiques les plus intéressantes sont issues d'observations patientes de simulations numériques, et, réciproquement, les simulations numériques les plus stimulantes sont celles qui donnent naissances à des questions où il s'agit d'analyser et démontrer les propriétés observées<fnref n="7" />.

### 3.2.1 Classifications à partir de chaînes de Markov

L'une des premières études analytiques des automates cellulaires asynchrones à l'aide de chaînes de Markov est due à Agapie et al. [5]. Ces auteurs se sont concentrés sur le cas de la mise à jour totalement asynchrone et pour des règles très spécifiques (symétriques par échange de 0 et 1 et à taux positifs <fnref n="8" />). On remarquera que le nombre de frontières entre zones de 0 et de 1 est un paramètre central de leur étude.

**Position de notre travail.** Les recherches effectuées au cours de notre doctorat (2004) nous ont amené à classer systématiquement le comportement des 64 ACE doublement quiescents [1, 97] (voir le chapitre 1). Rappelons que les règles ont été classées en fonction de leur temps de convergence moyen vers un point fixe. Nous avons montré que la variation de ce temps de convergence en fonction de la taille des anneaux se retrouvait dans les catégories suivantes : temps logarithmique, temps linéaire, temps quadratique, temps exponentiel et temps infini (règles non convergentes). Ces temps correspondent bien à des comportements qualitativement différents, repérables par l'inspection visuelle des diagrammes espace-temps. Regnault et al. ont étendu ces résultats au cas de l'α-asynchronisme [98]; Chassaing et Gerin ont considéré un modèle continu par passage à la limite pour des tailles d'anneau tendant vers l'infini [44].

Avec Lucas Gerin, nous avons également considéré le cas de règles bidimensionnelles avec une mise à jour totalement asynchrone [91]. Cette étude a conduit au repérage de règles au comportement métastable : on n'observe pas de convergence vers un point fixe si on se limite à des temps « raisonnables » alors que l'on pense qu'il existe à chaque instant une probabilité non-nulle d'atteindre le point fixe en quelques pas de temps. La clarification de ce phénomène de métastabilité nous a amené, lors d'une collaboration avec Jörg Hoffmann et Hector Palacios, à utiliser des techniques de planification sous contraintes afin de montrer qu'une de ces règles métastables avait en effet une convergence vers un point fixe avec un temps exponentiel en la taille de la grille [133].

Les lecteurs souhaitant en savoir sur les techniques d'analyse par chaînes de Markov pourront se reporter à l'entrée proposée pour une encyclopédie des systèmes complexes [85] ainsi qu'à l'article de synthèse proposé pour la revue *Natural Computing* <fnref n="9" /> [87] (voir aussi les deux premiers chapitres de ce mémoire).

<footnote n="7">7. Rappelons qu'originellement, *theoria* et *praxis* forment un couple indissociable et seule une connaissance réelle et approfondie d'un domaine peut donner lieu à une théorie ou un théorème. (Les Grecs anciens n'auraient donc jamais dit « ceci est théorique » dans le sens : « ceci est pure spéculation »,...)</footnote>

<footnote n="8">8. Une règle est dite à taux positifs si chaque état peut être atteint avec une probabilité non-nulle pour chaque état du voisinage.</footnote>

<footnote n="9">9. Cet article étend et corrige les résultats présentés dans les ref. [75] et [78].</footnote>
#### 3.2.2 Analyse des densités asymptotiques

Comme nous l'avons vu ci-dessus, un paramètre clé pour étudier les systèmes asynchrones est l'étude de la densité asymptotique. Fukś et Skelton ont réussi à donner l'expression exacte de celle-ci dans le cas $\alpha$-asynchrone pour un ensemble de règles bien choisies [113].

Avec Henryk Fukś, nous avons poursuivi cette direction en considérant des approximations de champ moyen qui prennent en compte, non pas seulement la densité de cellules à l'état 1, mais la densité des motifs d'ordre $k$ donné [111]. Cette approche s'appuie sur la théorie des structures locales (local structure theory) développée par Gutowitz [128] en 1987. Notre étude prédit correctement l'apparition de transitions de phase pour les règles où cela se produit effective-ment, ce qui est un premier pas, mais l'approximation est telle qu'elle ne permet pas d'estimer correctement la valeur du seuil critique.

#### 3.2.3 Modèles m-asynchrones

Les propriétés des automates cellulaires telles que l'injectivité, la surjectivité, la permutivité, etc. ont fait l'objet d'un grand nombre d'études analytiques. En 2012, Manzoni a étudié la façon dont ces propriétés pouvaient être redéfinies dans le contexte des automates cellulaires asyn-chrones [166]. Dennunzio et al. ont approfondi ce travail en développant la notion d'automate cellulaire *m-asynchrone*, pour laquelle les possibilités de définition de la fonction de mise à jour sont définies avec des outils de probabilités avancées [57]. Leur cadre d'étude est suffisamment large pour permettre de décrire des probabilités de mises à jour différentes pour chaque cellule, et ce même dans le cas où le système est infini. Nous nous référerons à un article de synthèse de Formenti pour une description des différents résultats obtenus avec ce modèle [106].

Les questions qui se posent à l'issue de l'examen de cette partie touchent donc à la définition de la nature de l'asynchronisme et de sa position au sein des automates cellulaires probabilistes.

### 3.3 Calculer avec des automates cellulaires asynchrones

Nous nous intéressons maintenant aux contributions liées aux capacités calculatoires des automates cellulaires asynchrones, en décrivant de façon brève les questions et les techniques qui émanent de ce thème.

#### 3.3.1 Simulation de modèles (a)synchrones par des modèles (a)synchrones

Nous avons vu dans les chapitres précédents que le comportement des règles simples bi-naires était souvent fortement affecté par un changement de mise à jour. Si l'on s'autorise à uti-liser un nombre d'états arbitraire, peut-on simuler le comportement synchrone avec un modèle asynchrone, c'est-à-dire construire des modèles qui soient parfaitement robsutes à l'asynchronisme ? Nakamura a été l'un des auteurs pionniers sur la question du calcul avec des automates cellulaires asynchrones [176, 175]. Cet auteur décrit différentes techniques pour construire des règles asynchrones qui soient universelles au sens de Turing et a montré comment simuler une règle classique avec $q$ états avec une règle asynchrone à $3q^2$ états. L'idée de Nakamura est qu'une cellule doit « attendre » ses voisines et ne faire sa transition que quand elle est sûre que celles-ci sont « au même temps » qu'elle. Après une mise à jour, elle garde son ancien état à disposition des cellules en retard sur elle, afin que les voisines puissent faire le bon calcul.

On pourra se reporter au travail de Lipton et al. [157], Toffoli [241] et Nehaniv [179] pour des constructions similaires. La construction de Nakamura a également été améliorée par Lee,
Peper et leurs collaborateurs, qui n'utilisent « que » $q^2 + 2q$ états pour leur simulation [152, 190]. Peper et al. ont également examiné le cas non classique où une cellule pouvait activer les cellules du voisinage et ont montré que le coût en nombre d'états pouvait être réduit à $O(q\sqrt{q})$ [191].

On trouvera chez Takada et al. d'autres résultats de ce type, notamment l'existence d'une règle asynchrone, symétrique par rotation, qui utilise 15 états sur un voisinage de von Neumann et qui est universelle au sens de Turing<fnref n="10" />.

En 1978, Golze a montré comment simuler une règle *n*-dimensionnelle synchrone à l'aide d'une règle asynchrone à *n* + 1 dimensions [124]. Cette solution a de nombreux avantages, mais on peut la considérer comme une sorte déploiement de la technique de Nakamura sur une dimension supplémentaire. Wang a généralisé cette construction au cas où la règle d'origine n'était pas déterministe mais malheureusement sans positionner son travail par rapport aux travaux antérieurs, ce qui rend difficile la comparaison avec les travaux de Nakamura et Golze [251]. Dennunzio et al. ont également proposé des techniques de simulation et de calcul en mode asynchrone, avec une estimation du ralentissement causé par la mise à jour asynchrone [56].

### 3.3.2 Dépendance à l'ordre de mise à jour

Une propriété centrale dans l'analyse des systèmes asynchrones est ce que nous pourrions désigner par « non-recouvrement des influences » : Si deux cellules *c* et *c'* sont telles que leur voisinage n'ont aucune cellule en commun, alors les trajectoires suivies par le système seront les mêmes si *c* est mise à jour avant *c'* ou l'inverse, ou si les deux sont mises à jour simultanément. L'ordre de mise à jour peut donc influencer ou non les trajectoires selon les formes du voisinage et les états générés par la fonction de transition locale.

En 2001, Gács a été un des premiers auteurs à regarder de près cette propriété [114]. Il a montré que bien que la propriété d'être insensible à l'ordre des mises à jour était indécidable, mais qu'il existait des conditions suffisantes permettant de la vérifier. Mortveit, McAuley et al. ont considéré le cas des automates cellulaires élémentaires et ont regardé à quelle condition des mises à jour cycliques produisaient des orbites dont la forme ne dépend pas de l'ordre de mise à jour [160, 161, 159]. Leur étude a conduit à identifier 104 règles élémentaires qui ont une telle propriété d'indépendance à la mise à jour; elle les a en outre conduits à proposer une représentation originale des règles de transitions locales (à comparer avec la notation par transitions actives que nous avons donnée au chapitre 1.2 [1, 97]).

Récemment, Perrot et ses collaborateurs ont introduit des outils d'analyse qui reposent principalement sur les relations de dépendances entre cellules induites par la relation « est mis à jour avant » [193, 186]. Ces techniques sont transposées de l'univers des réseaux booléens asynchrones [183, 12]. En considérant différentes relations d'équivalence induites par la mise à jour, les auteurs parviennent à estimer quelles sont les règles maximalement sensibles au changement de mise à jour et celles qui ne le sont pas.

Le problème de l'insensibilité à l'ordre de mise à jour a également été considéré par Worsch qui a montré que l'on pouvait construire un simulateur universel au sens de Turing qui ait cette propriété [254]. Son étude généralise celle de Golze en considérant un large éventail de méthodes de mise à jour. Ce travail soulève de nombreuses questions, en particulier celui de bien définir la notion de simulation d'une règle asynchrone par une autre règle asynchrone

<footnote n="10">10. Cette règle est également universelle dans le sens où elle peut construire toutes les configurations finies que l'on souhaite dans une partie de la grille.</footnote>
(voir aussi la ref. [13] pour des considérations similaires sur les automates cellulaires probablistes).

Notons également que Vielhaber a proposé un cadre formel où, pour une règle fixée, il s'intéresse au cas où le calcul de fonctions binaires sur des anneaux (Z/nZ) se fait en fixant seulement l'ordre de mise à jour des cellules [247]. Il a pour cela utilisé l'ACE 57 et a cherché à généraliser son approche pour construire des modèles universels au sens de Turing.

#### 3.3.3 Généralisations

Dès 1978, Priese s'est intéressé à regarder les automates cellulaires asynchrones bidimensionnels comme des cas particuliers de systèmes de réécriture (systèmes de Thue) [197]. Dans ce cadre, on considère que plusieurs cellules peuvent être modifiées en même temps et les propriétés de ces systèmes sont établies par équivalence aux réseaux de Petri. Zielonka lui a ensuite emboîté le pas en regardant comment les règles asynchrones pouvaient être utilisées pour décrire les situations de concurrence (concurrency) qui se produisent dans les systèmes distribués [51]. Pighizzini a par la suite clarifié les résultats de Zielonka [194] et des résultats similaires sur les automates cellulaires asynchrones de Büchi ont été présentés par Muscholl au même moment [174]. Droste [63] et Kuske [64, 144, 145] ont également généralisé et précisé le cadre posé par Zielonka et Hagiya et al. [129].

Mentionnons enfin le champ de recherche prometteur de la conception de circuits électroniques fonctionnant sur un modèle d'automates cellulaires asynchrones. Peper, Lee, et leurs collaborateurs en sont les principaux artisans. Ils développent un modèle où les calculs sont réalisés avec des particules qui suivent un mouvement brownien et qui interagissent dans des portes spécifiques [4, 3, 151, 192]. Ces auteurs proposent plusieurs façons de construire des circuits universels au sens de Turing qui sont insensibles aux délais introduits par les mouvements aléatoires des particules [149, 154].

Schneider et Worsch ont également proposé une règle à trois états qui permet de simuler des circuits insensibles aux délais [223]. Lee et al. ont ensuite généralisé leur travail en prenant comme outil les automates cellulaires qui conservent la masse (number-conserving cellular automata) [153].

## 3.4 Modéliser avec des automates cellulaires asynchrones

Dans cette partie, nous donnons cet aperçu des travaux liés à l'asynchronisme en examinant quelques réalisations liées au domaine de la modélisation. Le sujet est tellement vaste qu'il est hors de notre portée d'en donner une vision complète, nous souhaitons seulement éclairer quelques points.

### 3.4.1 Théorie des jeux et écologie

Huberman et Glance ont été parmi les premiers auteurs à mettre en lumière l'existence d'artefacts liés à la mise à jour : ce qu'ils désignent sous ce terme (artifacts) est le fait que certains comportements ne sont observés qu'en mode synchrone. Ils ont remis en question la validité des observations faites par simulation numérique sur des modèles spatiaux du dilemme du prisonnier [136]. Leurs travaux montrent que de nouvelles conclusions émergent, quant à la viabilité des phénomènes coopératifs, pour peu que l'on s'autorise à changer le mode de mise à jour des systèmes.
Cette question a été reprise par Newth et Cornforth qui ont également montré que de nouveaux états de coopération entre joueurs pouvaient être observés dans un cadre asynchrone et absents du cadre synchrone [181].

Grilo et Correia se sont également intéressés à ce problème et ont utilisé le mode de mise-
à-jour α-asynchrone [126]. Leur étude révèle que des changements continus sur le taux de syn-
chronisme peut induire des variations brutales du comportement. Il serait intéressant d'appro-
fondir ces observations, notamment en examinant si ces changements observés sont des transi-
tions de phase du second ordre. Saif et Gade ont quant à eux observé des transitions de phase
du premier ordre entre des états où tous les joueurs trahissent et des états où la coopération
et la trahison coexistent [217]. Dans tous ces travaux, on retrouve l'idée que le comportement
synchrone est soit trompeur, soit trop restrictif par rapport à la richesse de comportement des
modèles.

Ruxton et Saravia se sont intéressés à l'importance de la mise à jour dans un contexte écolo-
gique où l'on cherche à comprendre la colonisation d'un environnement par une espèce [216].
Les auteurs plaident pour un examen détaillé de procédures de mise à jour et disent que les
modèles doivent ajuster ces données structurelles en fonction de ce qui s'observe sur le terrain.
Ces arguments sont liés à ceux, plus généraux, de l'apparition de phénomènes émergents en
écologie et de la fiabilité des observations issues des simulations numériques [209, 42]<fnref n="11" />.

3.4.2 Phénomènes de synchronisation physiques et biologiques

Avec un point de vue assez proche de celui de Turing dans ses travaux sur la morphoge-
nèse [244], Gunji a utilisé les automates cellulaires asynchrones pour analyser la formation de
motifs chez les mollusques [127]. Une autre modélisation intéressante d'un phénomène bio-
logique est donnée par Messinger et al., qui ont examiné comment les plantes pouvaient syn-
chroniser les ouvertures et fermetures de leurs stomates de manière à obtenir un comportement
adéquat<fnref n="12" /> [171].

Du côté de la physique, mentionnons les travaux de Le Caër [148] qui a analysé les tran-
sitions de phase dans des automates cellulaires stochastiques sur des grilles triangulaires et
carrées. Cet auteur observe une différence de nature des transitions de phase selon la grille
utilisée et compare ses observations au modèle d'Ising. Radicchi et al. ont conduit des études
similaires et observent un changement de phase entre un comportement « ferromagnétique »
et « antiferromagnétique » induit par la probabilité de mise à jour [198].

3.4.3 Résolution de problèmes

Tomassini et Venzi [242], Capcarrere [40] et Nehaniv [178] ont étudié comment des règles asynchrones pouvaient être utilisées pour résoudre le problème de la classification de la densité (cf. chapitre 7) et le problème de synchronisation globale (cf. chapitre 8). Les lecteurs intéressés par ce thème peuvent se rapporter à l'étude par Vanneschi et Mauri, dans laquelle se trouve une discussion intéressante sur les modèles cités ci-dessus [245].

Dans le même ordre d'idées, Suzudo s'est intéressé aux modèles asynchrones qui génèrent
des motifs non-triviaux [237, 238]. Il classe ses motifs selon trois catégories : damiers, bandes
et « sabloïde » (*sand-like*). Dans ces travaux, l'asynchronisme est principalement utilisé pour
s'assurer que le nombre de particules est conservé mais c'est également un ingrédient utile pour

<footnote n="11">11. On notera également une étude du rôle de la mise à jour dans le comportement du célèbre modèle de Sakoda-Schelling de ségrégation spatiale [137].</footnote>

<footnote n="12">12. Je préfère ce terme à celui d'optimal, qui n'a sans doute pas sa place dans le contexte biologique...</footnote>
générer des motifs réguliers à l'aide de règles locales. On pourra se rapporter à nos travaux sur la classification de la densité en deux dimensions pour des liens avec cette thématique [73] (voir aussi le chapitre 7).

Beigy et Meybodi ont quant à eux proposé une piste prometteuse en concevant des systèmes asynchrones qui réalisent des opérations d'apprentissage et proposent d'appliquer leurs méthodes au contrôle de réseaux mobiles [18].

Enfin, mentionnons les travaux de Lee et al. [150] et de Huang et al. [135] qui ont conçu des modèles avec des motifs auto-reproducteurs avec des mises à jour asynchrones (*self-timed cellular automata*).

## 3.5 Autres systèmes complexes

### 3.5.1 Liens aux systèmes multi-agents

On remarquera dans les travaux de Cornforth et al. la mention de système multi-agents asynchrones mais, de façon intéressante, leurs modèles sont plutôt des automates cellulaires usuels [52]. En revanche, le travail de Comer a lui bien considéré des modèles multi-agents classiques, définis avec le logiciel Netlogo, mais les modèles qu'il a étudiés (aide à la décision pour l'armée ou pour la finance) sont trop éloignés de notre travail pour que nous puissions établir des liens [49].

On pourra également consulter le travail de Tošić pour une discussion sur le lien entre système multi-agents asynchrones et automates cellulaires [243]. Dans le chapitre 6, nous présenterons une analyse des systèmes multi-agents simples et de l'importance de regarder de près leur mise à jour.

Şamiloğlu et al. ont examiné les effets de l'asynchronisme dans la formation de groupes de particules en déplacement [220]. Leur modèle d'asynchronisme repose sur l'introduction de délais; ils constatent que la cohésion des groupes s'amenuise à mesure que les délais augmentent.

Lors du séjour post-doctoral d'Antoine Spicher, nous avons examiné la question de la « tra-duction » d'un système multi-agent séquentiel en un automate cellulaire asynchrone [233]. Nous avons défini des automates cellulaires transactionnels dans lesquels les mouvements des particules-agents sont synchronisés et où un pas de temps des agents correspond à un en-chaînement de trois pas temps successifs de l'automate cellulaire. L'avantage de ce mode de mise à jour est qu'il supprime les effets de biais liés à la mise à jour séquentielle des agents. Nous avons illustré l'existence de tels biais, et leur suppression en nous intéressant au cas de la diffusion limitée par agrégation (*diffusion-limited aggregation*), un modèle particulièrement bien étudié en physique statistique.

On notera que les automates cellulaires de gaz sur réseau (Lattice-Gas Cellular Automata, LGCA) peuvent être vus comme un « pont » entre la mise à jour centrée sur les agents et la mise à jour centrée sur les cellules. Appliquer une forme d'asynchronisme dans un tel modèle ne va pas de soi et nous avons proposé, lors du travail de thèse d'Olivier Bouré, un premier modèle d'automate cellulaire de gaz sur réseau asynchrone [30].

### 3.5.2 Autre modèles

Les effets de l'asynchronisme dans les réseaux de régulation génétiques (formels) a donné lieu à toute une série d'études. Aracena et al. ont introduit des outils formels permettant de dire dans quelle mesure des mises à jour sont équivalentes [12]. Demongeot et al. [55], et
Noual [182], ont développé ces recherches et évalué la robustesse des systèmes et leur sensibilité aux variations structurelles (ajout de liens entre éléments, etc.).

La question des effets de la mise à jour a également été prise en compte pour les réseaux de neurones. nous pouvons citer le travail de Scherrer [222], et celui de Taouali et al. [239] qui ont proposé des distinctions intéressantes entre différents niveaux d'asynchronisme.

Évoquons aussi le contexte du calcul amorphe (amorphous computing), dans lequel Stark décute des capacités de calcul d'un milieu d'unités disposées aléatoirement et subissant des mises à jour aléatoires [235, 234]. Cet auteur suggère, comme nous le montrerons dans la troisième partie du mémoire, que l'aléa peut avoir un rôle positif dans la réalisation de tâches de calcul.

Pour finir cette visite du paysage de la littérature scientifique ayant trait à l'asynchronisme, mentionnons que l'asynchronisme a également été étudié dans le contexte des réseaux d'appli-cations couplées (coupled-map lattices) [158, 210, 2] et dans le contexte des processus d'exclusion asymétrique (Asymmetric Exclusion Process, ASEP) avec les travaux de Rajewsky et al. [199].

Il existe bien sûr bien d'autres modèles de systèmes complexe dans lequel l'asynchronisme a été pris en compte, avec plus ou moins d'attention, mais nous avons tenu ici à présenter ceux qui nous paraissent les plus proches du modèle clé des automates cellulaires.

En somme, il semble que seule une partie infime de l'univers des automates cellulaires asynchrones ait été explorée à ce jour. Nous demandons donc :

**Question 8.** Les automates cellulaires asynchrones forment-ils un ensemble spécifique, qui demande une théorie propre et des outils propres, ou doit-on plutôt considérer les règles asynchrones comme des points particuliers de l'ensemble plus vaste des automates cellulaires probabilistes ?

**Question 9.** Qu'est-ce qu'un bon protocole expérimental pour estimer la robustesse des modèles à une perturbation comme l'asynchronisme ?

Quels sont les paramètres qui peuvent servir à cette estimation ?

**Question 10.** À quel point les phénomènes de transitions de phase sont-ils fréquents lorsqu'on opère des perturbations continues de la méthode de mise à jour ?

**Question 11.** Quelles sont les possibilités de définir et de construire une simulation d'un système asynchrone par un autre système asynchrone ?
# Deuxième partie

## Approche expérimentale des systèmes complexes
<figure><img src="image_16.png" /></figure>
# Modèle de Greenberg-Hastings

Ce chapitre expose un travail effectué en collaboration avec Hugues Berry à partir de 2010 [21]. Il nous permet de décrire les comportements de transitions de phase et d'examiner la classe d'universalité de la percolation orientée. Il est à noter nous avons également étudié ces transitions de phase dans différents systèmes à états binaires : automates cellulaires élémentaires [68] et jeu de la vie [70]. Un article présentant ce sujet a également été publié dans une conférence invitée lors du colloque Solstice'09 [69].

Le phénomène de réaction-diffusion est observé dans une large gamme de situations. Le travail de Turing sur la morphogenèse figure comme l'une des premières modélisations du phénomène [244]. Turing a proposé d'imaginer comment des composés chimiques fictifs, les *morphogènes*, peuvent agir et former spontanément des motifs uniquement par des mécanismes locaux d'amplification, d'inhibition et de diffusion, c'est ce qu'on appelle la *réaction-diffusion*. Par la suite, de nombreux modèles de réaction-diffusion ont été proposés pour expliquer différents phénomènes, par exemple la pigmentation des mollusques [143] ou les battements du cœur [163].

Nous allons présenter une version discrète des systèmes de réaction-diffusion. Le modèle que nous étudions est une variation probabiliste de la règle de Greenberg-Hastings [125]. Il s'agit d'un modèle parmi les plus simples pour étudier les phénomènes de réaction-diffusion. L'idée principale qui régit la règle locale de l'automate cellulaire est que les cellules sont dans un état quiescent, appelé état *neutre*, et deviennent *excitées* avec une certaine probabilité si au moins un de leurs voisins est excité. Une fois excitée, une cellule devient *réfractaire* et prend un pas de temps ou plus pour redevenir neutre. L'effet de ces règles simples est de permettre la propagation d'ondes qui ne s'atténuent pas avec la distance, contrairement aux ondes mécaniques ou aux ondes créés par la diffusion d'une substance telle qu'une phéromone.

En dépit de son apparente simplicité, ce modèle possède une grande richesse de comportement. Nous nous intéressons ici au *changement qualitatif* qui se produit quand la probabilité de transmission de l'état excité varie : dans le cas d'une grille infinie, en diminuant la probabilité d'excitation par un voisin, on passe d'un état global où les ondes vivent « infiniment longtemps » à un état où les ondes ont tendance à disparaître et où l'état tout-neutre agit comme un attracteur [103, 71]. Comme nos simulations se déroulent sur des grilles finies, nous devrons
<figure><img src="image_17.png" /><figcaption>FIGURE 4.1 – Règle de transition locale du modèle de Greenberg-Hastings</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>FIGURE 4.2 – Observations de la règle de Greenberg-Hastings probabiliste synchrone avec deux valeurs du taux de transmission $p_T$. En haut : $p_T = 0.4$, phase sous-critique, on atteint l'état tout-neutre rapidement. En bas : $p_T = 0.6$, phase sur-critique avec observation d'un état stationnaire. Les cellules en blanc et orange sont respectivement neutres et excitées, les autres couleurs indiquent les cellules réfractaires.</figcaption></figure>

estimer la distorsion engendrée par la taille de la grille (effets de taille finie, finite-size effects en anglais).

Ce modèle a principalement été étudié sur des grilles régulières et avec des règles locales déterministes (voir p. ex. la ref. [7] pour une des premières références). Copelli et Campos ont considéré le cas où les règles locales étaient appliquées sur des réseaux petit-monde [50], et Doba a étudié le cas de graphes finis de forme arbitraire [61].

## 4.1 Présentation du modèle

Le système est une grille finie $\mathcal{L} = \{1, \dots, X\} \times \{1, \dots, Y\}$ de taille $(X, Y)$. L'espace d'états est $Q = \{0, \dots, M\}$ : l'état 0 est l'état neutre, l'état $M$ est l'état excité, les états de 1 à $M-1$ sont les états réfractaires. Le voisinage d'une cellule $c$ est noté $\mathcal{N}_c$, on note $x_c^t$ l'état d'une cellule $c$ au temps $t$.

La figure 4.1 décrit la règle locale de l'automate cellulaire. Notons $E_c^t$ le nombre de cellules excitées dans $\mathcal{N}_c$ au temps $t : E_c^t = |\{c' \in \mathcal{N}_c : x_{c'}^t = M\}|$. La règle de Greenberg-Hastings
<figure><img src="image_19.png" /><figcaption>FIGURE 4.3 – Évolution de la densité de cellules excitées en fonction du temps $d_M(t)$ pour $M = 4$ et un voisinage de von Neumann.</figcaption></figure>

(A) Évolution pour un seul échantillon avec $L = 400$ et $p_T = 0.45$ (état sous-critique, en violet), $p_T = 0.46$ (état critique, en rouge), $p_T = 0.47$ (état sur-critique, en vert).

(B) Courbe en échelle log-log avec des moyennes pour 30 échantillons avec $L = 800$ et $p_T = 0.4595$ (violet), 0.4600 (rouge) et 0.4605 (vert). Les zones grisées indiquent la déviation par rapport à la moyenne. Le trait en pointillé indique une décroissance compatible avec l'hy- pothèse de percolation orientée : $d_M(t) \propto t^{-0.451}$. Repris de la ref. [21].

s'écrit [125] :

$$ \forall t, \forall c, \quad x_c^{t+1} = \begin{cases} M & \text{si } x_c^t = 0 \text{ et } E_c^t > 0 \text{ avec probabilité } p_T, \\ x_c^t - 1 & \text{si } x_c^t \in \{1, \dots, M\}, \\ 0 & \text{sinon,} \end{cases} \qquad (4.1) $$

autrement dit :

* Une cellule neutre qui a au moins une cellule excitée dans son voisinage devient excitée avec probabilité $p_T$ et reste neutre sinon.

* Une cellule excitée ($M$) devient réfractaire à l'état $M-1$.

* Une cellule réfractaire décrémente son état jusqu'à devenir neutre.

Notons simplement que la règle peut s'appliquer pour différents voisinages $N_c$ et même un voisinage de taille non-uniforme, comme lorsque l'on travaille sur des grilles avec des conditions aux bords non-périodiques. Dans la suite, sauf mention contraire les expériences présentées utiliseront un voisinage de von Neumann avec des bords périodiques.

## 4.2 Transitions de phase

Nous allons évaluer l'effet de la variation de la probabilité de transmission.
Quand la probabilité de transmission $p_T$ est suffisamment élevée, le système se stabilise sur un état stationnaire où $d_M$ oscille autour d'une valeur. Ceci correspond à l'état *actif* du système. Quand la probabilité $p_T$ baisse en deçà d'un seuil critique, on atteint l'état *d'extinction* dans lequel toute activité cesse. Ces deux comportements sont exposés sur la figure 4.2 : on y distingue une différence claire entre une tendance rapide à l'extinction (quelques dizaines de pas de temps) et un état stationnaire, qui, quoique métastable, peut se maintenir sur des temps très longs avec une densité moyenne de cellules excitées qui oscille autour d'une valeur moyenne.

Notons $d_M(t)$ la densité de cellules à l'état $M$ au temps $t$. La figure 4.3 montre les évolutions de $d_M(t)$ pour différentes valeurs de $p_T$. On remarque que sur une échelle log-log (fig. 4.3-B), la convergence vers un état stationnaire dans la phase active correspond à une forme convexe de la courbe alors que l'état d'extinction est lui repérable par une courbe concave. Notons qu'un changement infime de la valeur de $p_T$ permet de passer d'un comportement à un autre et de repérer $p_{T_c}$, la valeur de la probabilité critique qui sépare les deux régimes.

Selon les lois de la physique statistique, on s'attend à ce que le système suive des lois de puissance au voisinage du seuil critique [132]. On peut comprendre l'apparition de telles lois par l'existence d'une forme d'invariance d'échelle. En particulier, on s'attend à observer $d_M(t) \sim t^{-\delta}$ lorsque $p_T = p_{T_c}$, ce qui signifie que le seuil critique est repéré lorsque la courbe est droite dans une échelle log-log (fig. 4.3-B). De façon remarquable, un même exposant critique peut être observé pour des systèmes de nature différente et on appelle *classe d'universalité* l'ensemble des systèmes qui sont décrits par les mêmes exposants critiques. Le jeu de la vie mis à jour avec un mode $\alpha$-synchrone a lui aussi par exemple une transition de phase qui dépend du taux de synchronisme $\alpha$ et on mesure les mêmes exposants critiques que ceux trouvés ici [70, 69].

Ce comportement peut être mis en relation avec le phénomène de percolation [32]. Il existe de nombreux types de phénomènes de percolation, qui sont regroupés dans des catégories appelées classes d'universalité, avec la particularité que les différents modèles d'une même classe partagent les mêmes exposants critiques. Cette forme particulière d'« universalité » exprime le fait que des mécanismes avec des règles locales très différentes peuvent conduire à des comportements globaux similaires.

La classe d'universalité de la *percolation dirigée* (ou percolation orientée) a été observée dans de nombreux systèmes. Parmi les premières références, citons l'automate cellulaire de Domany-Kinzel [141, 62]. Dans notre travail, nous avons également observé que la percolation dirigée apparaissait dans le Jeu de la vie asynchrone [24, 70] et dans la dynamique asynchrone des automates cellulaires élémentaires [68, 212]. Pour le cas du modèle de Greenberg-Hastings probabiliste, notre étude a été motivée par l'évaluation du système d'amibes que nous présenterons dans le chapitre 9) et on a mesuré $\delta = 0.451$ comme exposant critique [71], ce qui correspond bien à la valeur attendue pour la classe d'universalité de la percolation dirigée [132, 184].

Notons que la valeur du seuil critique que nous avons mesurée, $p_T = 0.4600$, a été obtenue en itérant le processus qui consiste à repérer les changements de courbure sur une échelle log-log. Il faut ainsi réaliser des moyennes sur un nombre suffisant d'échantillons et calibrer le temps de mesure de façon adéquate, en faisant croître la taille progressivement. Dans notre cas, nous avons été jusqu'à faire des mesures pour des grilles de taille $L = 1200$ [21].
<figure><img src="image_20.png" /><figcaption>FIGURE 4.4 – Effet d’un changement de la valeur de *M* sur le seuil critique $p_{T_c}$. Repris de la ref. [21].</figcaption></figure>

## 4.3 Robustesse du phénomène

On peut réitérer l'expérience qui consiste à mesurer la valeur du seuil critique en changeant plusieurs paramètres. Commençons par examiner l'effet de la valeur *M*, c'est-à-dire du nombre d'états non-neutres du modèle. La figure 4.4 expose comment la valeur du seuil critique $p_{T_c}$ varie en fonction de *M*. Sans surprise, plus *M* est grand et plus grande est la valeur du seuil critique, et on peut inférer que cette valeur tend vers 1/2 pour *M* grand. En effet, quand le nombre d'états est trop grand, la ré-excitation d'une cellule par une onde de réaction-diffusion devient improbable et on retrouve un phénomène de percolation classique.

Lors de notre collaboration avec Bernard Girau, Nikolaos Vlassopoulos et Hugues Berry au sein du projet AMYBIA <fnref n="13" />, nous avons utilisé des dispositifs de calcul parallèle de type FPGA (field-programmable gate arrays)) [248] pour mesurer rapidement et précisément la valeur du seuil critique $p_{T_c}$. Ces mesures ont révélé que pour $M = 14$, c'est-à-dire que pour un modèle avec un assez grand nombre d'états, la valeur du seuil critique était de $p_{T_c} \sim 0.503$, avec une précision inférieure à $10^{-3}$, ce qui montre une différence nette avec le seuil 1/2. Nous sommes donc face à un nouveau problème ouvert : savoir si l'on a bien un seuil qui tend vers 1/2 pour de grandes valeurs de *M* ou si un décalage avec 1/2 peut exister.

Plus surprenante encore fut l'observation d'une égalité parfaite entre les valeurs obtenues pour les couples de valeurs pair-impair qui se suivent ($M = 2k$ et $M = 2k + 1$). Nous n'avons pas de démonstration de cette observation, même si l'on perçoit intuitivement que le voisinage de von Neumann joue un rôle central dans ce phénomène d'égalité.

## 4.4 Perturbation de la topologie

Nous évaluons maintenant l'effet de l'introduction de défauts dans la grille. Nous considérons deux types de défauts : (a) une cellule peut devenir défectueuse et ne plus répondre aux excitations des voisines; (b) les liens entre cellules peuvent devenir défectueux et ne plus relayer l'information d'une cellule à l'autre. Ces deux défauts sont introduits au départ et restent

<footnote n="13">13. https://amybia.loria.fr/</footnote>
<figure><img src="image_21.png" /><figcaption>FIGURE 4.5 – Évolution du seuil critique $p_{T_c}$ en fonction de taux de cellules manquantes et en fonction du taux de liens manquants (carrés). Les courbes sont obtenues avec 15 échantillons, $M = 4$, une taille de grille de $L = 1200$ et un voisinage de von Neumann. Les positions des défauts sont modifiées d'un échantillon à l'autre. Repris de la ref. [21].</figcaption></figure>
<figure><img src="image_22.png" /><figcaption>FIGURE 4.6 – Observations de la transition de phase avec un taux 40% de cellules manquantes (A) ou 40% de liens manquants (B). Les autres paramètres restent inchangés (cf. fig. 4.5.). Repris de la ref. [21].</figcaption></figure>

fixes au cours du temps.

La figure 4.5 montre l'effet de ces perturbations. Comme on pouvait s'y attendre, le seuil critique augmente avec le taux de défauts. Ceci s'explique facilement du fait que les défauts empêchent une bonne propagation des excitations à travers la grille et qu'il faut donc que la probabilité de transmission soit plus grande pour compenser cette atténuation.

Nous avons néanmoins été surpris de constater la détermination du seuil critique devient plus difficile à mesure que le taux de défauts croissait. Tout se passe comme si la transition entre le régime d'extinction et le régime actif était « floutée » par l'introduction de défauts. La figure 4.6 montre les résultats des simulations pour 40% de cellules manquantes et 40% de liens manquants. Il est à noter que comparé aux graphiques précédents, le pas de variation est ici de $10^{-3}$. On constate que là où on avait pour cette variation un net changement de courbure en échelle log-log, on a désormais des courbes assez droites, ce qui complique l'identification du seuil critique.

## 4.5 Développements analytiques

Les résultats qui viennent d'être présentés ont été obtenus à l'aide de simulations numériques. Peut-on obtenir des confirmations de ces observations par l'analyse mathématique ? Avec Hugues Berry, nous avons conduit une analyse de champ moyen de cette transition de phase. Cette étude a conduit a l'établissement d'une loi de proportionnalité inverse : la valeur du seuil critique varie en $C/N$ où C est une constante et N est le nombre moyen de voisins par cellule. L'approximation du champ moyen donne $C = 1$ alors que les études expérimentales donnent $C \sim 2$. La figure 4.7 montre comment le seuil critique varie en fonction de différents voisinages, réguliers ou irréguliers, et de leur valeur correspondante N.

Il est à noter que Reyes et Laroze ont confirmé cette observation et l'ont même étendue au cas des « graphes petit-monde » (small-world networks) [206, 205]. Soto Forero et Ceballos ont
<figure><img src="image_23.png" /><figcaption>FIGURE 4.7 – Illustration de la proportionnalité entre $p_{T_c}$ et $1/N$, où N est le nombre moyen de voisins. Les carrés correspondent à différents voisinages ; les cercles à $M = 4$ et au voisinage de von Neumann avec différents taux de défauts. Les triangles correspondent au voisinage de von Neumann avec $M$ variant de 2 à 10. La courbe rouge correspond à la fonction $p_{T_c} = 2/N$. Repris de la ref. [21].</figcaption></figure>
quant à eux réalisé une étude de la règle de Greenberg-Hastings sur des graphes avec des liens
dynamiques, en examinant en particulier des stratégies pour maintenir la phase active, et ce
selon différents scénarios [232].

**4.6 Problème inverse : diagnostic décentralisé**

À partir de ces observations, notant la grande robustesse de cette loi, nous avons proposé d'inverser le processus pour en faire un système de *diagnostic décentralisé* [122]. Le problème se pose ainsi : supposons que l'on ait un système constitué de composants en interaction locale qui peuvent tomber en panne à chaque pas de temps. Comment faire en sorte que le système puisse détecter de manière autonome quand le taux de composants défaillants franchit un seuil d'alerte fixé à l'avance ?

Notre idée est simple. Si on imagine que des défauts surviennent en mettant certaines cel-
lules hors-jeu, ceci va changer la connectivité moyenne des cellules et transformer le système
en le faisant passer d'un état sur-critique à un état sous-critique. La détection de ce change-
ment de phase peut permettre de détecter, de manière collective et non centralisée, que le taux
de défauts a passé un certain seuil.

Cette idée a fait l'objet du stage de Master de Nicolas Gauville, co-encadré avec Irène Mar-covici [122]. Nous y reviendrons dans la conclusion de ce mémoire.

Nous pouvons clore ce chapitre en relevant quelques questions.

**Question 12.** Comment expliquer l'invariance du seuil selon les couples de valeur paire-
impaire pour *M* et pour le voisinage de von Neumann ?

**Question 13.** Le processus de mesure des transitions de phase (seuils critiques et exposants critiques) étant très gourmand en calcul, comment l'améliorer et l'automatiser de façon à explorer des grands espaces de règles ? Est-il préférable d'utiliser des calculateurs classiques ou des outils dédiés tels que les FPGA ou les GPGPU (*general-purpose graphical processing units*) ?

**Question 14.** Peut-on utiliser le phénomène du déplacement du seuil critique en fonction de la topologie pour concevoir un système de diagnostic décentralisé ?
# Un modèle de formation d'essais

Nous considérons ici un phénomène collectif, la formation d'essais, comme exemple de système complexe où le hasard joue un rôle structurant. Le contenu de ce chapitre reprend une partie de la thèse d'Olivier Bouré, que nous avons co-encadrée avec Vincent Chevrier de 2010 à 2013 [26]. Ce travail a donné lieu à une publication en conférence [29] puis à une version longue dans la revue *Natural Computing* [30]. En 2018, une synthèse reprenant les observations précédentes en les précisant a été publiée dans un Festschrift dédié à Eric Goles [90].

Examinons maintenant un modèle de mouvement collectif. L'automate cellulaire que nous allons utiliser dérive d'une classe particulière d'automates, appelés *automates de gaz sur réseaux*, en anglais *lattice-gas cellular automaton* (LGCA). Ce modèle a été inventé pour étudier les mouvements des particules de gaz ou de liquides dans les années 1970 et jusqu'à présent ils ont été principalement utilisés dans ce cadre. Nous allons ici sortir de ce contexte et nous intéresser à leur utilisation en biologie. Nous suivons ici la proposition d'Andreas Deutsch, qui a proposé en 1996 un modèle de gaz sur réseaux pour étudier la formation d'essais [58].

La particularité des gaz sur réseaux est que chaque cellule peut contenir une ou plusieurs particules, jusqu'à quatre, chaque particule ayant une direction parmi les quatre directions cardinales. Initialement, les particules sont réparties de manière aléatoire uniforme et avec des directions aléatoires. À chaque pas de temps, les particules vont interagir avec leurs voisines en changeant leur direction, puis elles vont avancer dans la direction qui est la leur. Nous nous intéressons aux conditions qui permettent l'apparition de phénomènes de formation de motifs de particules avec des déplacements cohérents des particules.

## 5.1 Une première observation

Avant de nous attacher aux détails du modèle et à sa description formelle, observons simplement le phénomène d'auto-organisation qui est présenté sur la figure 5.1. Avec un peu d'imagination, on peut voir des oiseaux former un essaim ou des poissons former un banc. Nous voyons que les particules se groupent et se déplacent en diagonale : comment comprendre ce phénomène ? Quel est le rôle du hasard dans la formation de cette bande diagonale ? Ce regroupement est-il robuste aux changements de valeur des paramètres et aux différentes perturbations du modèle ?
<figure><img src="image_24.png" /><figcaption>FIGURE 5.1 – Évolution du système à partir d'une condition initiale aléatoire pour $L = 32$, $\sigma = 2.0$ et $d_{ini} = 0.2$.</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>FIGURE 5.2 – Représentation des étapes d'interaction et de propagation.</figcaption></figure>

## 5.2 Définition du modèle

On note $\mathcal{L} = (\mathbb{Z}/X.\mathbb{Z}) \times (\mathbb{Z}/Y.\mathbb{Z})$ la grille avec des conditions aux bords périodiques, c'est-à-dire que l'espace est torique. Notons que l'on pourrait également travailler sur $\mathcal{L} = \mathbb{Z}^2$.

Chaque cellule comporte quatre *canaux*, chacun des canaux étant associé à une direction cardinale *n*, *e*, *s*, *w* qui correspondent respectivement aux directions nord, est, sud, ouest. Un canal qui contient une particule est *occupé*, et libre sinon.

L'état d'une cellule est donc représenté par un quadruplet $(q_n, q_e, q_s, q_w) \in Q = \{0, 1\}^4$, où 0 et 1 représentent respectivement l'absence ou la présence d'une particule dans un canal.

Dans ce chapitre, nous noterons les configurations comme des *fonctions* afin d'éviter la sur-charge d'indices (pour le canal et pour la cellule). L'espace des configurations est noté $\mathcal{E}_n = Q^\mathcal{L}$.

La règle globale est notée $F: \mathcal{E}_n \to \mathcal{E}_n$ et son application se décompose en deux temps :

1. l'étape d'interaction, où les particules sont redistribuées au sein de la même cellule, et

2. l'étape de propagation, où les particules sont déplacées d'une cellule à ses cellules voil-
sines.

Ce dernier mouvement est simple : chaque particule se déplace dans la cellule qui correspond à sa direction. Une particule du canal nord dans une cellule $(x, y)$ arrive dans le canal nord de la cellule $(x, y + 1)$; s'il se trouvait une particule dans ce canal, comme les mouvements sont synchrones, cette particule se déplace aussi au nord et il n'y a pas de collision. Formellement :
$$x^{t+1} = F(x^t) = F_{\text{prop}} \circ F_{\text{interact}}(x^t).$$

Décrivons d'abord l'étape de propagation, qui est la plus simple.

En notant $x = (x_n(c), x_e(c), x_s(c), x_w(c))$ et $y(c) = (y_n(c), y_e(c), y_s(c), y_w(c)) = F_{\text{prop}}(x)$, il vient, pour toute cellule $c \in \mathcal{L}$ :

$$ 
\begin{array}{l@{\qquad}l@{\qquad}l}
y_n(c) = x_n(c - v_n) & \text{avec} & v_n = (0, 1); \\
y_e(c) = x_e(c - v_e) & & v_e = (1, 0); \\
y_s(c) = x_s(c - v_s) & & v_s = (0, -1); \\
y_w(c) = x_w(c - v_w) & & v_w = (-1, 0).
\end{array}
$$

Passons à l'étape d'interaction. Soit $q = (q_n, q_e, q_s, q_w)$ l'état d'une cellule; nous appelons un tel état une tuile. Nous allons replacer cette tuile par une tuile contentant le même nombre de particules, selon une règle stochastique. On note $N(q) = q_n + q_e + q_s + q_w$ le nombre de particules d'une tuile $q$ et $\pi(q)$ l'ensemble des tuiles ayant même nombre de particules : $\pi(q) = \{q' \in \{0, 1\}^4, N(q') = N(q)\}$.

Nous associons à chacune de ces tuiles un poids défini par une fonction $w : \{0, 1\}^4 \to \mathbb{R}^+$. La probabilité $p_w(q)$ de sélectionner une tuile $q$ après application de l'étape d'interaction vaut alors

$$p_w(q) = \frac{w(q)}{\sum_{q' \in \pi(q)} w(q')}.$$

Pour calculer ce poids, nous introduisons maintenant les paramètres suivants :

- Le flux local $\varphi : Q^4 \to \mathbb{Z}^2$ d'une cellule $c \in \mathcal{L}$ est la quantité de mouvement des particules de cette cellule. En notant $x(c) = (q_n, q_e, q_s, q_w)$, on a :

$$\varphi(x(c)) = q_n \cdot v_n + q_e \cdot v_e + q_s \cdot v_s + q_w \cdot v_w.$$

- Le champ directeur $D \in \mathbb{Z}^2$ d'une cellule $c$ est la somme des flux locaux des voisines de $c$ :

$$D(x, c) = \varphi(x, c + v_n) + \varphi(x, c + v_e) + \varphi(x, c + v_s) + \varphi(x, c + v_w).$$

Notons $< \cdot, \cdot >$ le produit scalaire de deux vecteurs de $\mathbb{Z}^2$. Pour une force d'alignement $\sigma$, l'étape d'interaction est donnée par la probabilité $P(x \to x_I)$ de remplacer une configuration $x$ par une configuration $x_I$ :

$$P(x \to x_I) = \prod_{c \in \mathcal{L}} \frac{\exp\{\sigma < D(x, c), \varphi(x_I(c)) >\}}{Z(x, c)},$$

où :

$$Z(x, c) = \sum_{q \in \pi(x(c))} \exp\{\sigma < D(x, c), \varphi(q) >\}$$

est le facteur de renormalisation.

Le rôle de $\sigma$ est de favoriser l'apparition d'une tuile alignée avec le flux local et de défavoriser l'apparition des tuiles dont le flux local est opposé à celui de la cellule considérée.
## 5.2.1 Invariant du damier

Par construction cet automate possède une quantité conservée non désirée. En effet, si nous appelons paires et impaires les particules qui sont respectivement situées sur une case paire ou impaire, c'est-à-dire l'équivalent d'une case noire ou blanche du damier, alors on peut vérifier que le nombre de particules paires et impaires est échangé à chaque pas de temps.

Notons $(x^t)$ l'évolution du système, et $\mathcal{L}_0 = \{c = (c_x, c_y) \in \mathcal{L}, c_x + c_y \in 2\mathbb{Z}\}$ et $\mathcal{L}_1 = \mathcal{L} \setminus \mathcal{L}_0$ les ensembles de cellules paires et impaires, respectivement, $N_0(t) = \sum_{c \in \mathcal{L}_0} N(x^t(c))$ et $N_1(t) = \sum_{c \in \mathcal{L}_1} N(x^t(c))$ le nombre de cellules paires et impaires, respectivement. On peut vérifier que l'application des règles des gaz sur réseaux donne toujours : $(N_o, N_1)(t+1) = (N_1, N_0)(t)$.

La présence de cet invariant est un défaut du modèle puisque, contrairement à la conservation du nombre de particules, il ne résulte pas d'un choix délibéré. C'est ce qui amène certains auteurs à préférer l'utilisation d'une grille hexagonale pour les modèles de gaz sur réseaux. On pourra se rapporter au travail de Barberousse et Imbert pour une discussion plus approfondie sur les simulations par gaz sur réseaux [17]. Notons que notre construction d'automates de gaz sur réseaux avec mise à jour asynchrone, quoi qu'elle complique la définition du modèle, permet de se débarrasser de cet invariant indésirable [26, 30].

## 5.2.2 Récurrence de la chaîne de Markov

La deuxième propriété remarquable est que la chaîne de Markov qui décrit l'évolution du système est récurrente : si à un temps donné le système se trouve dans une configuration $x$ cette même configuration sera revisitée infiniment souvent. Ceci a une conséquence importante : sur des grilles finies, les motifs que nous observerons seront toujours asymptotiquement instables, c'est-à-dire que quand nous observerons des motifs stables, ils seront en réalité métastables. En d'autres termes, ils seront stables sur des durées très longues, excédant largement tous les temps mesurables, mais ils seront à terme voués à la destruction.

Notons que dans ce qui suit le terme de *motif* sera utilisé de manière informelle pour désigner un ensemble de configurations ayant la même apparence visuelle. La récurrence du système implique qu'une connaissance finie du système demanderait d'étudier les motifs avec deux quantités : leur *attractivité*, c'est-à-dire leur probabilité d'apparaître en partant d'une condition initiale aléatoire et leur *stabilité*, c'est-à-dire le temps moyen durant lequel ils seront observables. Nous laissons ces pistes comme des problèmes ouverts.

À ce jour peu de résultats analytiques ont été donnés sur ce modèle. Les approximations de champ moyen ont été utilisées avec un certain succès pour prédire le passage d'un état ordonné à un état désordonné (voir ref. [36] et ref. [59, Chap. 8]) mais de telles approches ne permettent pas de rendre compte de la richesse de motifs que l'on peut observer dans ce modèle. Signalons qu'Irène Marcovici a également étudié des éléments invariants de ce modèle dans sa thèse de doctorat [167, Chap. 2.6].

## 5.3 Exploration des motifs stables

## 5.4 Quantification de l'ordre

On notera $\gamma(x)$ l'alignement moyen d'une configuration $x \in \mathcal{E}_n$. Ce paramètre évalue dans quelle mesure les particules d'une cellule ont tendance à être alignées avec les cellules voisines;
<figure><img src="image_26.png" /><figcaption>FIGURE 5.3 – Évolution de l’alignement moyen pour la trajectoire observée sur la fig. 5.1: $L = 32$, $d_{ini} = 0.2$, $\sigma = 2.0$.</figcaption></figure>

il est défini par

$$ \gamma(x) = \frac{1}{4N(x)} \sum_{c \in \mathcal{L}} < \varphi(x, c), D(x, c) > . $$

La division par 4 assure que $\gamma$ a une valeur dans $[-1, 1]$ : une valeur proche de 1 (resp. -1) indique qu’en moyenne les particules sont alignées (resp. « anti-alignées ») avec les particules voisines, une valeur de 0 indique une absence d’alignement.

### 5.4.1 Formation de bandes diagonales

La figure 5.3 montre l'évolution temporelle de l'alignement moyen pour la même évolution que celle qui est montrée dans la figure 5.1.

Cette évolution peut être divisée en trois phases : la première est la formation de la bande, qui survient en un temps relativement court. Dans un second temps la bande diagonale s'« affirme » et devient de plus en plus régulière. Après environ un millier d'étapes, le système a atteint un état stationnaire métastable.

Pour estimer le temps nécessaire à la formation de la bande, on répète l'expérience en re-prenant des conditions initiales aléatoires et pour chaque trajectoire, on mesure le temps pour atteindre la valeur $\gamma = 0.5$. En effet, à ce stade, la bande diagonale ne peut disparaître qu'avec une probabilité infinitésimale (métastabilité).

La figure 5.4 montre l'histogramme montrant la distribution des temps de formation de la bande, mesurés pour $L = 32$. L'échantillon est de taille 10 000 et la densité initiale est $d_{ini} = 0.2$. On observe une distribution qui semble suivre une loi de Poisson. En doublant la taille des dimensions de la grille ($L = 64$), on remarque une légère augmentation du temps moyen de la formation de la bande mais un resherrement de la distribution. Ceci montre que le phénomène devient plus régulier avec des grandes tailles; on pourra se rapporter à l'article de Bouré et al.
<figure><img src="image_27.png" /><figcaption>FIGURE 5.4 – Distribution du temps de formation d'une bande diagonale pour $L = 32$ et $L = 64$.</figcaption></figure>

pour plus détails [30].

### 5.4.2 Phase avec motifs à damiers

Observons maintenant ce qui se produit si l'on part d'une plus haute densité tout en gardant la force d'alignement constante ($\sigma = 0.2$). Prenons par exemple $d_{ini} = 0.4$, ce qui correspond à un doublement de la valeur du paramètre.

La figure 5.5 montre l'évolution du système pour ce réglage : nous observons alors un phénomène surprenant puisque les particules ont désormais une tendance à l'**anti-alignement** ! En effet, les simulations montrent que des zones de couleurs homogènes apparaissent assez rapidement et que dans ces zones les couleurs alternent comme sur un damier. En y regardant de plus près, on peut assez facilement comprendre d'où provient la stabilité de ces zones : à chaque pas de temps la composition de l'étape d'interaction et de l'étape de propagation fait

<figure><img src="image_28.png" /><figcaption>FIGURE 5.5 – Évolution du système à partir d'une condition initiale aléatoire pour $L = 32$, $\sigma = 2.0$ et $d_{ini} = 0.4$.</figcaption></figure>
<figure><img src="image_29.png" /><figcaption>FIGURE 5.6 – Évolution de l’alignement moyen pour la trajectoire observée sur la fig. 5.5: $L = 32$, $d_{ini} = 0.4$, $\sigma = 2.0$.</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>FIGURE 5.7 – Distribution du temps de formation d'une configuration-damier pour $L = 64$ et $L = 128$.</figcaption></figure>
<figure><img src="image_31.png" /><figcaption>FIGURE 5.8 – Evolution of the system from a random initial configuration. The grid size is $L = 32$, the alignment force is $\sigma = 4.0$ and the initial density is equal to $d_{ini} = 0.2$.</figcaption></figure>

que les directions des particules se conservent. En effet, lors de l'étape d'interaction les particules d'une cellule « essaient » de s'aligner avec les particules voisines mais, comme le même mouvement se produit dans les cellules voisines, celles-ci changent également leur orientation et après l'étape de propagation, les directions sont inchangées.

Bien sûr des fluctuations apparaissent et les zones de damier ont tendance à dériver sur la grille. Lorsque deux zones se rencontrent, des instabilités surviennent aux frontières. Les zones peuvent alors croître ou décroître, et parois fusionner jusqu'à former une unique zone de damier. De façon intéressante on notera qu'un phénomène similaire se produit avec la dynamique de la règle minorité avec une mise à jour totalement asynchrone [204] ou avec un modèle d'Ising qui tend à l'anti-alignement des spins.

Sur la figure 5.6, on observe l'évolution de l'alignement moyen sur la même trajectoire que celle de la figure 5.5. On voit que l'alignement moyen décroît de manière régulière jusqu'à ce que se forme un damier unique, qui forme alors un équilibre métastable. La figure 5.7 permet de se faire une idée du temps nécessaire à la formation d'un damier : le temps mesuré correspond au temps d'atteinte de la valeur $\gamma = -0.5$.

### 5.4.3 Phase d'amas

Observons maintenant ce qui se produit si l'on reprend la densité initiale de départ ($d_{ini} = 0.2$) et si on double la valeur de la force d'alignement : $\sigma = 4$.

La figure 5.8 montre l'évolution du système : on observe qu'un état stationnaire apparaît, dans lequel des groupes de particules se déplacent de façon cohérente selon les quatre directions cardinales. Nous appelons cet état, l'état d'amas. Ces amas restent cohérents lorsqu'ils se rencontrent et donnent l'impression de se traverser quasiment sans interagir. Il y a néanmoins des fluctuations dues à l'aléa qui font que les groupes gagnent ou perdent des particules au fil du temps.

La figure 5.9 montre l'évolution temporelle de l'alignement moyen $\gamma$ pour la même trajectoire que celle de la figure 5.8. Nous mesurons le temps nécessaire à atteindre la valeur $\gamma = 0.8$ et montrons les distributions de ce temps dans la figure 5.10. Nous sommes assez surpris d'observer que pour de petites tailles de grille ($L < 128$), on trouve des trajectoires qui ne forment pas cet état d'amas; le système se stabilise alors sur un état dit « état serpent » (voir [26, 30]).

En somme, ce modèle montre bien en quoi une approche expérimentale des systèmes complexes reste nécessaire : si l'on prend l'étape d'interaction seule, on a un modèle qui n'est pas
<figure><img src="image_32.png" /><figcaption>FIGURE 5.9 – Évolution de l’alignement moyen pour la trajectoire observée sur la fig. 5.8: $L = 32$, $d_{ini} = 0.2$, $\sigma = 4.0$.</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>FIGURE 5.10 – Distribution du temps de formation d'une configuration à motifs d'amas pour $L = 128$ et $L = 256$ (100 échantillons).</figcaption></figure>
bien différent des modèles « classiques » de magnétisation tels que les modèles d'Ising. Il a suffi d'ajouter l'étape de propagation pour que l'on arrive dans un domaine quasiment inconnu. Nous constatons aussi que le passage de l'ordre au désordre, bien loin de se limiter à deux comportements-type, comme dans le cas du modèle de Greenberg-Hastings par exemple, comporte plusieurs motifs stables, dont les trois principaux sont la bande, les damiers et les amas. Il y a donc *plusieurs* transitions de phase à étudier si l'on veut disposer d'une bonne cartographie du modèle. Des éclairages extrêmement limités peuvent être apportés par l'analyse mais ceux-ci ne parviennent pas à notre connaissance à expliquer toute la richesse des phénomènes observés. On constate donc que la modélisation et la compréhension des mouvements collectifs, aussi simples soient-ils au niveau local, reste une question scientifique de taille.

Finissons ce chapitre en relevant ces questions :

**Question 15.** Comment mesurer avec précision les transitions de phase existantes entre l'état désordonné et les différents motifs ?

**Question 16.** Comment évaluer l'attractivité et la *stabilité* des motifs observés ?
Ce chapitre présente des travaux effectués en collaboration avec Vincent Chevrier [45, 46] et développés en 2012 lors du stage de Master 2 de Selma Belgacem [19]. Nous avons cherché à donner aux systèmes multi-agents un cadre formel proche de celui des automates cellulaires et à tirer profit de ces descriptions pour élargir le spectre des observations faites par simulation numérique sur le modèle particulier des turmites (ou fourmis de Langton).

## 6.1 Des modèles discrets simples

Dans un article fondateur sur la « vie artificielle » publié en 1986 [147], Langton écrit que « Le comportement global d'une société est un phénomène émergent, qui résulte de toutes les interactions locales de ses membres. (...) Nous savons que des comportements complexes peuvent émerger à partir des interactions de parties très simples. Les colonies d'insectes so-ciaux fournissent un bon sujet pour l'étude de la vie artificielle car elles montrent immédiate-ment un comportement complexe qui émerge des interactions entre des parties vivantes très simples. »<fnref n="14" />

La méthode poursuivie par Langton se rapproche de celle que Turing a empruntée lorsque celui-ci travaillait sur la morphogenèse [244] : au lieu d'essayer de prendre en compte de plus en plus d'aspects de la réalité, ce qui est souvent un travail sans fin, chercher plutôt à sim-plifier le modèle autant que faire se peut, jusqu'à identifier les mécanismes qui sont suffisants pour qu'un phénomène donné se produise. Langton a donc proposé de considérer un système simple, composé d'un ou plusieurs agents, qui agissent sur une grille bidimensionnelle avec des cellules ayant un état binaire, noté 0 et 1. Son but est double, d'abord trouver un cas illus-trant la complexité du passage du local au global pour un agent seul, puis, dans un second temps, observer ce qu'il se produit dans une « société d'agents ».

<footnote n="14">14. The global behaviour of a society is an emergent phenomenon, arising out of all of the local interactions of its members. [...] We know that complex behaviour can emerge from the interaction of very simple parts. Colonies of social insects provide a good subject material to the study of artificial life because they so readily exhibit complex behaviour emerging from the interaction of very simple living parts.</footnote>
<figure><img src="image_34.png" /><figcaption>FIGURE 6.1 – Evolution d’une turmite seule. **à gauche** : à partir d’une grille initialement vide (toutes les cellules à l’état 0, en blanc) ; **à droite** : à partir d’une unique cellule à l’état 1 (en bleu) aux coordonnées (1, 0).</figcaption></figure>

Le système est à temps et à états discrets et les agents, appelés fourmis de Langton, ou turmites selon le bon mot de Dewey [60], sont sans mémoire et suivent deux règles<sup>15</sup> :

(a) Une turmite qui est sur une cellule à l'état 0, transforme cet état en un 1, tourne à gauche et avance d'une case.

(b) Une turmite qui est sur une cellule à l'état 1, transforme cet état en un 0, tourne à droite et avance d'une case.

Langton a observé que le comportement d'une turmite seule était déjà un phénomène étonnant (figure 6.1). De plus, dans le cas où plusieurs agents étaient mis ensemble, des phénomènes de collaboration pouvaient survenir et mener à l'apparition de structures complètement différentes de celles observées dans le cas d'une turmite solitaire. Néanmoins, Langton est obligé de concéder que : « Il y a tellement de façons avec lesquelles ces fourmis virtuelles peuvent se rencontrer que nous n'avons pas encore pris en compte toutes les rencontres possibles »<sup>16</sup>. Notre but dans ce chapitre sera donc de poursuivre sur cette voie et de relever le défi posé par Langton en définissant différentes interactions ente turmites et en observant les modifications que ces différences entraînent.

### 6.1.1 Turmites

Il existe un certain nombre d'articles qui présentent des études avec une seule turmite [119, 25, 118, 164]. Partant d'une grille où toutes les cellules sont à l'état 0, la fourmi suit une trajetoire irrégulière pendant environ 10 000 pas de temps, après quoi elle entre sans crier gare dans un comportement cyclique qui lui fait décrire un chemin qui se translate (voir la figure 6.1). Différentes généralisations de cette situation ont été proposées [117, 116] mais, de façon surprenante, les systèmes à plusieurs turmites ont été peu étudiés jusqu'à présent. Les études de

<footnote n="15">15. On notera que Bunimovich and Troubetzkoy ont proposé des règles similaires dans un contexte de système de particules [33].</footnote>

<footnote n="16">16. "There are so many ways that these virtual ants can encounter one another that the transition rules have not yet been worked out for all of the possible encounters."</footnote>
Chopard et Droz [47], ainsi que celles de Beuret and Tomassini [23], sont les seules dont nous
avions connaissance jusqu'à la préparation de ce manuscrit. Nous avons néanmoins trouvé un
article de Wang et Xu décrivant un modèle multi-turmite utilisé pour des applications de cryp-
tage d'image (scrambling) [252]. Néanmoins, cette approche a été critiquée et il semble qu'une
seule turmite suffise à obtenir d'aussi bons résultats, voire de meilleurs [66].

6.1.2 Neuf variations

Comme le mentionnait Langton, étudier un système à plusieurs turmites n’est pas simple
du fait de la variété des interactions possibles entre turmites. Ceci se généralise au cas de la
plupart des systèmes multi-agents : même quand le comportement d’un agent est parfaite-
ment bien défini, il reste un large choix de possibilités pour définir ses interactions avec les
autres agents. Aussi, avec Vincent Chevrier, nous avons mis en place un formalisme permet-
tant de spécifier ces interactions dans un cas général [45, 46]. Ce formalisme s’appuie sur le
paradigme « influence-réaction » proposé par Ferber et Muller en 1996 [102]. Nous présentons
ici une instanciation de ce formalisme dans le cas d’un système à plusieurs turmites : notre idée
est qu’un tel système est suffisamment simple pour pouvoir se livrer à un travail complet de
formalisation, et suffisamment riche pour pouvoir nous permettre d’observer des comporte-
ments qualitatifs variés en fonction des définitions choisies.

6.2 Fondations

La présentation du formalisme suit le travail que nous avons effectué avec Vincent Che-
vrier [45], mais de manière allégée.

On note $\mathcal{L} = \mathbb{Z}^2$ la grille; chaque cellule $c \in \mathcal{L}$ a un état dans $\mathcal{Q} = \{0,1\}$. L'état général de la grille est noté $\mathbf{S} \in \mathcal{Q}^\mathcal{L}$. Soit $N$ le nombre de turmites, on notera $[N] = \{1, ..., N\}$ l'ensemble des turmites.

On assigne à chaque turmite *i* une position $P_i \in \mathcal{L}$ et une orientation $O_i \in \mathcal{D} = \{\mathbb{N}, \mathbb{E}, \mathbb{S}, \mathbb{W}\}$ correspondant respectivement aux directions nord, est, sud et ouest.

On note $\mathbf{P} = (P_1, \dots, P_N) \in \mathcal{L}^N$ et $\mathbf{O} = (O_1, \dots, O_N) \in \mathcal{D}^N$, le $N$-uplet des positions et orientations des turmites. Par extension avec la terminologie des automates cellulaires, on ap-
pelle *configuration* l'état général du système, qui est noté $\sigma = (\mathbf{S}, \mathbf{P}, \mathbf{O}) \in \mathcal{S} = \mathcal{Q}^\mathcal{L} \times \mathcal{L}^N \times \mathcal{D}^N$.

Avec ces notations, le système multi-turmite est un système dynamique discret sur $\Sigma$, et,
un pas de temps sera donné par l'application de la fonction de transition globale : $\Gamma : \Sigma \to \Sigma$.

Notre problème consiste maintenant à décrire $\Gamma$ sachant que :

(a) nous voulons mettre à jour les agents de différentes façons, et,

(b) nous souhaitons avoir différentes procédures de résolution de conflits.

Nous définissons donc $\Gamma$ avec deux fonctions auxiliaires :

(a) la fonction de mise à jour $\Delta$ et,

(b) la *procédure de résolution de conflits* $\xi$.

On note $\Gamma_{\Delta,\xi}$ la fonction de transition globale obtenue avec $\Delta$ et $\xi$. L'orbite d'un système est la suite des configurations $(\sigma(t))_{t \in \mathbb{N}} = \text{ORB}(\Delta, \xi, \sigma)$ obtenue avec : $\sigma(0) = \sigma$ et $\forall t \in \mathbb{N}$, $\sigma(t+1) = \Gamma_{\Delta,\xi}(\sigma(t))$.

La méthode de mise à jour est une fonction $\Delta : \mathbb{N} \to \mathcal{P}([N])$ où $\mathcal{P}(X)$ est l'ensemble des parties de $X$; cette fonction définit l'ensemble des turmites mises à jour à chaque pas de temps. Nous définissons trois fonctions de mise à jour $\Delta$ :
• $\Delta_s$ synchrone : les turmites sont toutes mises à jour simultanément à chaque pas de temps.
On a : $\Delta_s(t) = [N]$.

• $\Delta_c$ cyclique : les turmites sont mises à jour séquentiellement dans l'ordre de leur indice.
On a : $\Delta_c(t) = \{t \mod N + 1\}$.

• $\Delta_r$ aléatoire : les turmites sont mises à jour séquentiellement, mais dans un ordre qui varie à chaque pas de temps. On a : $\Delta_r(t) = \pi_k(t')$ où $t' = t \mod N, k = \lfloor t/N \rfloor$ et $(\pi_k)_{k \in \mathbb{N}}$ est une suite de variables aléatoires qui échantillonnent de manière uniforme l'ensemble des permutations des entiers de 1 à N.

Nous pouvons maintenant définir $\Gamma$ en spécifiant, de manière indépendante, d'une part l'évolution des états des cellules $\mathbf{S}$, d'autre part les évolutions des positions $\mathbf{P}$ et des orientations $\mathbf{O}$. L'évolution de l'état de la grille suit :

$$ \forall c \in \mathcal{L}, S_c(t+1) = \begin{cases} 1 - S_c(t) & \text{si } c \in \{P_i, i \in \Delta(t)\} \\ S_c(t) & \text{sinon.} \end{cases} $$

Cette règle dit que l'état $S_c(t)$ est modifié si une cellule $c$ contient au moins une turmite qui a été mise à jour (par $\Delta$).

Pour définir $(\mathbf{P}, \mathbf{O})(t)$, nous devons décrire les interactions. Premièrement, notons que les positions et orientations sont fixes pour les cellules non mises à jour : $\forall i \notin \Delta(t), (P_i, O_i)(t+1) = (P_i, O_i)(t)$. Pour une turmite $i \in \Delta(t)$, la façon de calculer $(P_i, O_i)(t+1)$ dépend de $\xi$; notons $(\tilde{P}_i(t), \tilde{O}_i(t))$ l'état que prendrait la turmite $i$ au temps suivant s'il n'y avait pas de conflit au temps $t$.

Notons $\mathbb{R}$ et $\mathbb{L}$ les rotations à droite et à gauche, respectivement, avec $\mathbb{R}(\mathbb{N}) = \mathbb{E}$, $\mathbb{L}(\mathbb{N}) = \mathbb{W},...$ On a alors les définitions suivantes de $(\tilde{P}_i(t), \tilde{O}_i(t))$ :

$$ \tilde{O}_i(t) = \begin{cases} \mathbb{R}(O_i(t)) & \text{si } S_{P_i(t)}(t) = 0, \\ \mathbb{L}(O_i(t)) & \text{si } S_{P_i(t)}(t) = 1. \end{cases} $$

et

$$ \forall i \in [N], \tilde{P}_i(t) = P_i(t) + dP(\tilde{O}_i(t)) $$

$$ \text{où } dP(\mathbb{N}) = (0, 1), dP(\mathbb{E}) = (1, 0), dP(\mathbb{S}) = (0, -1), dP(\mathbb{W}) = (-1, 0). $$

Nous sommes maintenant en mesure de définir $\xi$; nous le ferons selon trois versions.

1. Règle d'indépendance $\xi_{AL}$. Cette règle, notée Allow(AL), autorise les turmites à se déplacer sans tenir compte des conflits :

$$ \xi_{AL}: \forall i \in \Delta(t), (P_i, O_i)(t+1) = (\tilde{P}_i, \tilde{O}_i)(t). $$

2. Règle d'exclusion $\xi_{EX}$ : Quand un conflit survient, cette règle, notée Exclude(EX), interdit aux turmites de se déplacer et de tourner. Les conflits peuvent survenir dans deux cas :

— type A : une turmite cherche à aller dans une case occupée;

— type B : deux turmites ou plus cherchent à se déplacer dans la même case.

L'identification de ces conflits utilise une fonction $n$ qui compte le nombre de turmites dans une cellule $c \in \mathcal{L}$ étant donnée une configuration $\mathbf{P}$ :

$$ n: \begin{array}{ccc} \mathcal{L}^N \times \mathcal{L} & \rightarrow & \mathbb{N} \\ (\mathbf{P}, c) & \mapsto & |i \in [N], P_i = c|. \end{array} $$
<figure><img src="image_35.png" /><figcaption>FIGURE 6.2 – De la position (P, O) à la position (˜P, ˜O). On a: n[P, c₁] = 0, n[˜P, c₁] = 2, n[P, c₂] = 1, n[˜P, c₂] = 1, n[P, c₃] = 0 et n[˜P, c₃] = 1. Cette situation génère un conflit de type A avec la turmite 3 et un conflit de type B avec les turmites 1 and 2 et pas de conflit avec la turmite 4.</figcaption></figure>

La figure 6.2 montre un exemple de conflit de type A et de type B. Nous renvoyons aux ref. [45, 46] pour plus de détails sur les conflits.

La règle d'exclusion Exclude se définit alors par :

$$ \xi_{\text{EX}} : (P_i, O_i)(t+1) = \begin{cases} (\tilde{P}_i, \tilde{O}_i)(t) & \text{si la turmite } i \text{ n'est pas en conflit,} \\ (P_i, O_i)(t) & \text{sinon.} \end{cases} $$

3. La règle tourner-et-voir $\xi_{TS}$ : Cette règle est notée $\text{Turn}'n'$ See (TS) : les turmites en conflit ne bougent pas mais sont autorisées à tourner. On prend toujours : $O_i(t + 1) = \tilde{O}_i(t)$ et on a :

$$ \xi_{\text{TS}} : P_i(t+1) = \begin{cases} \tilde{P}_i(t) & \text{si la turmite } i \text{ n'est pas en conflit} \\ P_i(t) & \text{sinon.} \end{cases} $$

Nous avons donc trois méthodes de mise à jour et trois règles de résolution de conflit. Voyons donc si ces différences de définition du système amènent ou non à des différences notables de comportement, alors même que, rappelons-le, le comportement individuel de chaque turmite reste inchangé en dehors des interactions.

### 6.2.1 Cycles

On sait qu'une turmite seule ne peut avoir de comportement cyclique (au sens strict) puisqu'elle finit toujours par sortir de tout rectangle préalablement fixé [33, 47]. En revanche, cette propriété n'est plus vraie avec plusieurs turmites...

*Observation* 1. Pour le modèle *Allow* synchrone, un nombre pair de turmites placées horizontalement et orientées nord produisent un cycle. Formellement : pour $N \in 2\mathbb{N}$ et pour une condition initiale $\sigma = (\mathbf{S}, \mathbf{P}, \mathbf{O}) : \mathbf{S} = \mathbf{0}; \forall i \in [N], P_i = (i, 0), O_i = \mathbb{N}, \text{l'orbite } \text{ORB}(\Delta_{\mathbf{S}}, \xi_{\text{AL}}, \sigma)\text{ est cyclique.}$

Nous avons déterminé expérimentalement que la période du cycle varie comme $16N - 4$ et que le temps transitoire est de 0. De plus, les cellules visitées par les turmites se limitent à une zone rectangulaire de taille $3N \times 2N$.

La figure 6.3 montre un cycle avec 4 turmites. La configuration au temps $t = 60$ montre la fin du cycle, lorsque la configuration est identique à la configuration initiale.

Pour l'ensemble des conditions initiales décrites ci-dessus, le phénomène de cycle n'apparaît qu'avec la mise à jour synchrone et la règle *Allow*. Il est donc peu robuste.
<figure><img src="image_36.png" /><figcaption>FIGURE 6.3 – Phénomène d’horloge avec 4 turmites. Chaque turmite a sa propre couleur.</figcaption></figure>

### 6.2.2 Planeurs

Les planeurs (gliders) sont des phénomènes rares dans l'ensemble des simulations que nous avons conduites sur un système multi-turmite, c'est-à-dire qu'il a fallu conduire un grand nombre d'expériences « à la main » pour pouvoir les observer.

*Definition 1 (Planeurs).* On dit qu'une orbite $(\sigma(t))_{t \in \mathbb{N}}$ est un *planeur* si :

— toutes les turmites sont dans la même translation infinie, c'est-à-dire, pour tout $i \in [N]$ :

$$ \exists \rho \in \mathcal{L}, \exists T \in \mathbb{N}, \forall t \in \mathbb{N}, P_i(t+T) = P_i(t) + \rho \text{ et } O_i(t+T) = O_i(t), $$

— En partant d'une grille vide, la « trace » laissée par les turmites est nulle, c'est-à-dire :

$$ \mathbf{S}(0) = \mathbf{0} \text{ et } \forall c \in \mathcal{L}, \exists t \in \mathbb{N}, t' \ge t \implies S_i(t) = 0. $$

Ces planeurs sont des phénomènes analogues aux planeurs observés dans le Jeu de la vie. Le premier planeur que nous avons observé a été nommé *F-glider* [46]. Nous présentons ici le *B-glider* :

*Observation 2.* Pour la règle *Allow* quatre turmites placées en position carrée avec une orientation nord forment un planeur. Formellement : pour $N = 4$, pour $\Delta \in \{\Delta_s, \Delta_c, \Delta_r\}$, l'orbite $\text{ORB}(\Delta, \xi_{AL}, \sigma)$ obtenue avec la condition initiale $\sigma = (\mathbf{S}, \mathbf{P}, \mathbf{O}) : \mathbf{S} = \mathbf{0}; P_0 = (0,0), P_1 = (1,0), P_2 = (1,1), P_3 = (0,1); O_1 = O_2 = O_3 = O_4 = \mathbb{N}$} est un planeur.

La figure 6.4 montre quatre étapes de l'évolution du *B-glider*; ce planeur se déplace avec une distance de 2 cellules (horizontalement ou verticalement) tous les 12 pas.

On notera avec satisfaction qu'à la différence du *F-glider*, qui n'est observé qu'avec la mise à jour synchrone et la politique *Allow*, le *B-glider* est robuste aux changements de la méthode de mise à jour. Cependant, il n'est pas robuste aux changements de méthode de résolution des conflits.
<figure><img src="image_37.png" /><figcaption>FIGURE 6.4 – Quatre étapes dans la translation du B-glider.</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>FIGURE 6.5 – Deux blocages obtenus avec une distance initiale entre turmites de 52 et 56 cel- lules.</figcaption></figure>

### 6.2.3 Blocages

Nous présentons maintenant notre troisième classe de conditions initiales, qui produit un phénomène que nous appelons un *blocage* (stalemate).

*Definition 2.* Une orbite $(\sigma(t))_{t \in \mathbb{N}}$ contient un *blocage* si la position des turmites n'évolue plus après un certain temps :

$$ \exists t_0, \forall t \ge t_0, \forall i \in [N], P_i(t) = P_i(t_0). $$

*Observation 3.* Pour le mode synchrone *Turn' n' See*, deux turmites placées à une distance horizontale $k$ l'une de l'autre, avec des orientations orthogonales ouest et nord, produisent toujours un blocage si $k$ est un multiple de 4 et supérieur à 52. Formellement : pour $N = 2$, pour $k \in 4\mathbb{N}^*$ et $k \ge 52$ et $\sigma = \{\mathbf{S} = \mathbf{0}, P_1 = (0,0), O_1 = \mathbf{W}; P_2 = (k,0), O_2 = \mathbb{N}\}$, l'orbite $\text{ORB}(\Delta_s, \xi_{\text{TS}}, \sigma)$ contient un blocage.

La figure 6.5 montre deux blocages obtenus avec deux distances $k$. On notera que les blocages sont également observés pour $k < 52$, mais il n'y a pas de régularité dans la façon dont le phénomène se produit. En revanche, pour $k \ge 52$, nous pouvons garantir que les deux turmites interagissent toujours de la même manière. En effet, cette « distance de sécurité minimale » est telle que l'on peut s'assurer que chaque turmite génère bien son propre chemin et n'est pas « perturbée » par un chevauchement de sa trace et de la trace de l'autre turmite. Si cette condition est respectée, la turmite 2 croise toujours le chemin de la turmite 1 de la même manière :
elle suit le chemin, le contourne puis rattrape la turmite 1. Cela produit un conflit de type B qui aboutit toujours à une impasse.

En augmentant la valeur de $k$ de 4 cellules, on s'assure que les deux turmites suivent la même séquence de comportement avant de se rencontrer. Cette régularité est due à la périodicité spatiale de la construction du chemin, qui est invariante par une translation de (2, -2) (voir fig. 6.5). Nous observons également qu'une augmentation de $k$ de 4, augmente le temps de blocage de 104, un résultat en accord avec les résultats analytiques obtenus par Boon [25]. Le temps de blocage varie donc avec $k$ comme : $t_{st}(k) = t_{st}(52) + \frac{k-52}{4} \times 104$, avec la valeur expérimentale $t_{st}(52) = 11539$.

Nous n'avons observé de blocage qu'avec le mode synchrone *Turn'n'See*, c'est donc un phénomène peu robuste.

En résumé, nous avons décrit trois phénomènes qui résultent de collaboration entre turmites. Nous avons observé que, selon le cas considéré, il existe une grande variété de réponses du système aux variations du schéma de mise à jour et de la politique de résolution des conflits mais qu'en général les phénomènes collectifs sont peu robustes aux changements de définition du système, même si le comportement individuel des agents reste inchangé.

Nous laissons les lecteurs intéressés par une analyse détaillée de la robustesse de ces phénomènes consulter la partie 4 de la référence [19]; une étude des divergences et des convergences qui se produisent au niveau microscopique y est développée pour expliquer la robustesse et la sensibilité des trois phénomènes décrits ci-dessus.

Nous retenons les questions suivantes :

**Question 17.** Peut-on démontrer que partant d'une condition initiale avec un nombre fini de 1 sur la grille, une turmite seule finit toujours par s'échapper à l'infini en créant une « route » de même nature que celle observée pour une grille initialement vide ?

**Question 18.** Quels sont les autres phénomènes intéressants que l'on peut avoir avec un nombre quelconque de turmites ?

**Question 19.** Quel lien peut-on faire entre ce modèle et d'autres systèmes multi-agents simples comme celui des fourmis virtuelles par exemple ?
Troisième partie

Résolution de problèmes inverses
<figure><img src="image_39.png" /></figure>
7

Problème de la classification de la
densité

Ce chapitre nous plonge dans un nouvel aspect de la thématique de ce mémoire : l’apport de l’aléa pour créer une dynamique qui permette de résoudre des problèmes calculatoires <fnref n="17" />. Nous commençons par une question spécifique avec le problème de la classification de la densité. Les recherches sur le modèle unidimensionnel ont été publiées dans article court paru dans les actes de STACS’11 [72] et dans un article plus développé dans la revue *Theory of Computing systems* [76]. Entre 2012 et 2016, différents travaux d’extension aux grilles (AC bidimensionnels) ont été publiées dans des actes de conférence ou dans des revues [73, 34, 35, 93].

Le problème de classification de la densité est un problème-pivot de la théorie des auto-
mates cellulaires. Sa formulation est étonnamment simple : Comment un système dynamique
discret distribué peut-il atteindre un état de consensus qui représente l’état majoritairement
présent dans sa configuration initiale ?

Le problème est plutôt trivial dans la plupart des modèles de calcul mais la difficulté réside
ici dans le respect des contraintes suivantes :

1. *autonomie* : Il n'y a pas de tête ou d'opérateur pour faire le calcul. L'évolution du système se fait par des changements d'états de composants autonomes du système, les cellules.

2. *consensus* : La fin du calcul est atteinte lorsque le système atteint un état stable homogène où toutes les cellules sont dans un même état.

3. *localité* : Chaque cellule n'a qu'une vue partielle du système, restreinte aux voisins situés à une certaine distance.

4. *uniformité* : Les cellules évoluent en suivant une même règle locale, qui reste fixe avec le temps.

5. simplicité : L'état des cellules est binaire.

<footnote n="17">17. Par « dynamique », on peut même ici entendre le mot dans son sens étymologique, car *dunamis* indique originallement l'idée de potentiel, de possibilité gardée en réserve, de retenue dans l'accomplissement d'une chose, etc.</footnote>