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

HAL
open science

Auto-correction par automates cellulaires

Nassima Ait Sadi

► To cite this version:

Nassima Ait Sadi. Auto-correction par automates cellulaires. Automates cellulaires et gaz sur réseau [nlin CG]. 2025. http://arxiv.org/abs/2005.05577

HAL Id: hal-05337714

https://inria.hal.science/hal-05337714v1

Submitted on 29 Oct 2025

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
SORBONNE UNIVERSITÉ
(PIERRE ET MARIE CURIE)

MASTER EN MATHÉMATIQUES DE LA MODÉLISATION

UNIVERSITÉ DE LORRAINE
LABORATOIRE LORIA

# Auto-Correction par Automates Cellulaires

## Rapport de stage

**Nom** : Nassima AIT SADI

**Master** : Mathématiques de la modélisation – Sorbonne Université (Campus Pierre et Marie Curie)

**Tuteur de stage** : Nazim Fatès, Chargé de recherche à Inria, membre de l'équipe Mocqua au laboratoire LORIA, Université de Lorraine

**Lieu du stage** : Laboratoire LORIA, Université de Lorraine, Nancy.
Remerciements

Je tiens à exprimer mes remerciements les plus sincères à Nazim Fatès pour m'avoir proposé un thème de recherche aussi passionnant. Ce sujet, à la fois riche et stimulant, a éveillé ma curiosité scientifique à chaque étape de mon travail. Chaque fois que je m'immergeais dans les détails, je découvrais de nouvelles perspectives et j'étais profondément fascinée par les idées qui en émergeaient.

Je remercie également toute l'équipe Moqcua pour son accueil chaleureux et les échanges enrichissants qui ont jalonné ce stage.
Résumé

Ce rapport présente une étude des automates cellulaires appliquée aux problèmes de colo-
riage sur $Z^2$. Il se divise en trois chapitres correspondant à différentes étapes de notre investiga-
tion. Le premier chapitre est consacré à l'analyse théorique du problème des 3-coloriages, où nous
introduisons les concepts fondamentaux liés aux automates cellulaires et identifions des configu-
rations uniquement corrigibles, ainsi que les propriétés nécessaires pour qu'un automate puisse
résoudre ce problème. Le deuxième chapitre décrit la construction d'un automate cellulaire ca-
pable de corriger partiellement les erreurs dans le cadre des 3-coloriages, en exploitant des motifs
locaux et une correction orientée vers le nord et l'est. Nous y identifions les limites de correction
et les types d'erreurs persistantes, apportant ainsi une réponse partielle au problème. Le troisième
chapitre ouvre la réflexion sur les 4-coloriages à travers l'analyse d'une règle probabiliste, en po-
sant les bases pour de futures études sur la correction non directionnelle par automates cellu-
laires.
# Table des matières

<table><tr><td>Table des matières</td><td>5</td></tr></table>

<table><tr><td>1 Introduction</td><td>1</td></tr></table>

<table><tr><td>1.1 Les problèmes inverses dans le cadre des systèmes dynamiques</td><td>2</td></tr></table>

<table><tr><td>1.1.1 Les problèmes inverses en physique</td><td>2</td></tr></table>

<table><tr><td>1.1.2 Les problèmes inverses en Informatique</td><td>2</td></tr></table>

<table><tr><td>1.2 Les problèmes inverses dans le cadre des automates cellulaires</td><td>3</td></tr></table>

<table><tr><td>1.2.1 Auto-stabilisation par automate cellulaire</td><td>3</td></tr></table>

<table><tr><td>1.2.2 La classification de la densité</td><td>3</td></tr></table>

<table><tr><td>1.3 Auto-correction par automates cellulaires</td><td>6</td></tr></table>

<table><tr><td>1.3.1 État de l'art des coloriages par automates cellulaires</td><td>6</td></tr></table>

<table><tr><td>1.3.2 Cas des 3- coloriages</td><td>8</td></tr></table>

<table><tr><td>1.4 Auto-stabilisation sous perturbations permanentes</td><td>11</td></tr></table>

<table><tr><td>1.5 Organisation du Rapport</td><td>11</td></tr></table>

<table><tr><td>2 Coloriages par Automates Cellulaires</td><td>13</td></tr></table>

<table><tr><td>2.1 Notions fondamentales de la dynamique symbolique</td><td>13</td></tr></table>

<table><tr><td>2.1.1 Automates cellulaires</td><td>14</td></tr></table>

<table><tr><td>2.2 Coloriages par automates cellulaires</td><td>15</td></tr></table>

<table><tr><td>2.3 Existence de solution pour les 3-coloriages</td><td>15</td></tr></table>

<table><tr><td>2.3.1 Des configurations uniquement corrigibles</td><td>16</td></tr></table>

<table><tr><td>2.3.2 Des chemins à complétion obligatoire</td><td>17</td></tr></table>

<table><tr><td>2.3.3 Des perturbations finies non prises en compte dans la correction</td><td>18</td></tr></table>

<table><tr><td>2.3.4 Condition nécessaire pour une correction ternaire</td><td>23</td></tr></table>

<table><tr><td>2.3.5 Synthèse</td><td>25</td></tr></table>

<table><tr><td>3 Auto-correction partielle des 3-coloriages</td><td>27</td></tr></table>

<table><tr><td>3.1 Présentation de la règle locale</td><td>27</td></tr></table>

<table><tr><td>3.1.1 Pour quel comportement?</td><td>28</td></tr></table>

<table><tr><td>3.2 Exemples numériques</td><td>31</td></tr></table>

<table><tr><td>3.3 La stratégie de correction</td><td>32</td></tr></table>

<table><tr><td>3.3.1 Les motifs consommateurs d'erreurs :</td><td>33</td></tr></table>

<table><tr><td>3.4 Analyse de la règle</td><td>34</td></tr></table>

<table><tr><td>3.5 Étude des erreurs se propageant à l'infini</td><td>37</td></tr></table>

<table><tr><td>3.6 Synthèse</td><td>39</td></tr></table>

<table><tr><td>4 Exploration des 4-coloriages par automates cellulaires probabilistes</td><td>43</td></tr></table>

<table><tr><td>4.1 Préliminaires</td><td>43</td></tr></table>

<table><tr><td>4.1.1 Évolution des automates cellulaires</td><td>44</td></tr></table>

<table><tr><td>4.2 Auto-correction isotropique et probabiliste pour un 4-coloriage</td><td>44</td></tr></table>

<table><tr><td>4.2.1 Quel comportement? Quel rôle de l'aléa?</td><td>44</td></tr></table>

<table><tr><td>4.2.2 Quelle mise à jour pour les cellules?</td><td>45</td></tr></table>

<table><tr><td>4.3 Analyse de la règle corrigeant les 4-coloriages</td><td>46</td></tr></table>
<table><tr><td>4.3.1 Caractérisation des motifs sains des 4-coloriages</td><td>46</td></tr><tr><td>4.3.2 Correction de deux cellules adjacentes dans une région à diagonales</td><td>49</td></tr><tr><td>4.3.3 Synthèse</td><td>50</td></tr></table>
# Chapitre 1

# Introduction

> L'intelligence, ce n'est pas de ne
> pas faire d'erreurs, mais de savoir
> les corriger rapidement.

> — Bertolt Brecht

Quand on se blesse, même légèrement. C'est fascinant de voir à quel point notre corps sait
quoi faire. La peau, par exemple, ne reste pas longtemps en état blessé. Elle réagit tout de suite.
Il y a d'abord un peu de sang, puis une croûte se forme mais en dessous, un vrai travail de re-
construction a déjà commencé. Des cellules se multiplient, des tissus se reforment, et tout ça sans
qu'on ait à y penser. En quelques jours ou semaines, selon la gravité, la blessure disparaît ou laisse
une cicatrice, preuve que le corps a fait de son mieux pour réparer. C'est un processus qu'on tient
souvent pour acquis, alors qu'il illustre quelque chose de plus large : *la capacité d'un système à se
corriger lui-même*.

Ce phénomène, on le retrouve dans plein d'autres domaines. Dans la nature, par exemple, ou
même dans les systèmes techniques ou sociaux. On parle alors de *systèmes dynamiques*, ce sont
des ensembles qui évoluent dans le temps, interagissent avec leur environnement. Comme un
thermostat qui ajuste le chauffage quand il fait trop froid, ou un lac qui retrouve son équilibre
après une pollution temporaire. Il y a toujours cette idée de retour à un état stable, d'adaptation.
Ce n'est pas forcément parfait ni immédiat, mais le système tend à se stabiliser de lui-même.

Dans de nombreux systèmes dynamiques, qu'ils soient naturels ou artificiels, leur évolution
est rarement isolée des influences extérieures ou intérieures, qu'elles soient anticipées ou non.
Ces influences, appelées perturbations, peuvent résulter de phénomènes naturels, d'interventions
humaines ou encore de défaillances techniques, et sont susceptibles de modifier profondément
le comportement attendu du système. En physique, dans les systèmes mécaniques, électroniques
ou autres, la robustesse, qui est la capacité d'un système à maintenir ses propriétés essentielles
malgré des perturbations, est essentielle à la conception de dispositifs fiables. Par exemple, en
ingénierie des systèmes de contrôle, on cherche à garantir la stabilité d'un système face à des in-
certitudes dans les paramètres du modèle ou à des perturbations extérieures [31, 24]. En biologie,
certains systèmes, comme les réseaux génétiques, sont remarquablement robustes malgré leur
complexité et leur variabilité. Les cellules peuvent continuer à fonctionner même en présence de
mutations, de stress environnementaux ou de fluctuations moléculaires [16]. De plus, divers types
de perturbations peuvent être effectuées. Que ce soit des perturbations réalisées au niveau de la
condition initiale ou des perturbations générées, que ce soit par le système lui-même ou par des
facteurs extérieurs, au court de l'évolution du système [15, 2].

Face à de telles perturbations, une question essentielle se pose : comment intervenir sur le sys-
tème afin de le ramener vers un état souhaité, ou de le guider à retrouver son comportement at-
tendu ? C'est précisément dans ce contexte que s'inscrit l'étude *des problèmes inverses* [3]. Contrai-
rement à l'approche directe, qui consiste à suivre l'évolution du système à partir de conditions
initiales connues, les problèmes inverses se donnent un comportement cible et visent à remon-
## 1.2 Les problèmes inverses dans le cadre des automates cellulaires

Les automates cellulaires (AC) sont des modèles de systèmes dynamique discrets dans le temps, l'espace et les états, capables de simuler des dynamiques complexes à partir de règles locales simples. Chaque cellule évolue en fonction de l'état de ses voisines selon une règle de transition déterministe ou probabiliste. Utilisés à l'origine pour modéliser des phénomènes biologiques ou physiques, les AC trouvent aujourd'hui des applications variées allant de la théorie de la computation à la modélisation de systèmes naturels, en passant par l'intelligence artificielle et la cryptographie [22, 28, 20]. Les problèmes inverses dans le cadre des automates cellulaires consistent à se donner un motif final ou un certain comportement fixé au départ et chercher à remonter aux règles ou aux configurations initiales qui l'ont engendré si ces dernières existent. Ces problèmes sont non seulement mathématiquement délicats, mais ils posent aussi des défis computationnels majeurs. Leur application est essentielle dans divers thématiques notamment en cryptographie, Wolfram a exploré comment les automates cellulaires peuvent être utilisés pour générer des systèmes cryptographiques et les différents défis liés à l'inversion[30]. Ces problèmes sont souvent mal posés, car plusieurs configurations peuvent conduire au même état observé, rendant la tâche d'inversion instable. Cette difficulté a conduit à explorer des approches inspirées de l'auto-stabilisation, où l'automate cellulaire lui-même est utilisé non seulement comme système évolutif mais aussi comme outil de stabilisation. Dans ce contexte, l'auto-stabilisation agit comme un mécanisme interne permettant à l'automate de stabiliser un état perturbé à partir de données bruitées.

### 1.2.1 Auto-stabilisation par automate cellulaire

Le concept d'auto-stabilisation dans les processus computationnels a été introduit pour la première fois en 1982 par Dijkstra, qui a présenté des exemples de réseaux d'automates à états finis possédant une propriété d'auto-stabilisation non triviale [4]. Divers travaux ont été réalisés par la suite, notamment en utilisant les automates cellulaires [10, 18]. Les recherches sur l'auto-stabilisation par automates cellulaires se sont développées selon plusieurs axes. Des travaux pionniers, notamment ceux de Gács [10], ont démontré la possibilité d'un comportement fiable même en présence de fautes aléatoires, à l'aide de structures hiérarchiques complexes. Dans cet article [10], Gács construit un automate cellulaire unidimensionnel probabiliste capable de résister à des erreurs aléatoires et de se réorganiser pour retrouver un comportement correct à grande échelle. Il introduit une hiérarchie de blocs emboîtés, chacun surveillant et réparant les erreurs de niveau inférieur, illustrant ainsi une forme puissante d'auto-stabilisation distribuée. D'autres contributions, comme celles de Levin [18] ou Fatès et al. [6], ont montré que des automates cellulaires déterministes ou probabilistes peuvent stabiliser une configuration globale malgré des erreurs initiales, souvent en imposant des contraintes de symétrie, de pavage ou de voisinage.

Un exemple illustrant les limites de la dynamique locale des automates cellulaires dans la pré-diction des comportements globaux est le problème de la classification de la densité.

### 1.2.2 La classification de la densité

Le problème de la classification de la densité consiste à concevoir un automate cellulaire capable de converger vers un état homogène, tout 1 ou tout 0, selon que la densité initiale de 1 dans la configuration initiale soit supérieure ou inférieure à $\frac{1}{2}$. Bien qu'intuitivement simple, ce problème s'est révélé fondamentalement difficile pour des règles locales déterministes. En 1995, Land et Belew ont démontré qu'aucun automate cellulaire uniforme, à deux états ne peut le résoudre parfaitement [17]. Ce résultat été redémontré en utilisant des arguments simplifiés et été généralisés au cadre des automates cellulaires stochastiques [19]. Ce problème d'apparence simple met en évidence les limitations de l'auto-stabilisation purement locale dans certaines tâches globales, soulignant la tension entre l'information locale et la décision globale. Cependant, de nombreuses variantes du problème ont été considérées en allégeant les conditions imposées ou en considé-
rant de l'aléa dans les transitions. En particulier, Fukś a proposé de combiner deux règles locales dans l'objectif est d'avoir une solution répandant au problème [9] tandis que Fatès a présenté une famille de règles probabilistes qui permettent de réduire la probabilité de mal classifier les configurations à une valeur aussi petite que l'on veut [5]. L'idée est d'utiliser l'aléa et de combiner la règle élémentaire majorité avec la règle traffic afin de résoudre le dilemme existant entre la décision locale majoritaire et la propagation vers un état fixe [25, 23, 8, 7]. On présente dans la prochaine section une illustration détaillée sur la combinaison des deux règles afin de résoudre le problème de la classification de la densité.

## Les règles traffic et majorité

La règle traffic (appelée règle 184 dans la numérotation de Wolfram [29]) est une règle d'automate cellulaire unidimensionnel binaire. Cette règle modélise un système dans lequel chaque cellule représente une voiture (état 1) ou une case vide (état 0), les voitures avancent d'une case vers la droite si celle-ci est libre, sinon reste inchangée. Cette dynamique permet de déplacer l'information dans la configuration : les blocs de 1 ont tendance à se déplacer vers la droite, les blocs de 0 vers la gauche, quand les deux types de blocs se rencontrent, ils se neutralisent. Si leurs longueurs ne sont pas égales, le plus long des deux continue avec une longueur égale à la différence entre la longueur initiale des blocs de 1 et 0 révélant ainsi des structures qui reflètent la densité globale. La figure 1.1 représente deux diagrammes espace-temps de la règle traffic.

<figure><img src="image_3.png" /><figcaption>FIGURE 1.1 – Diagrammes espace temps de la règle 184. Les carrés blancs et noirs représentent les états 1 et 0 respectivement.</figcaption></figure>

La règle traffic a été étudiée dans le cadre du problème de la classification de la densité. Bien que ne soit pas en elle-même capable de résoudre le problème de classification, elle est souvent utilisée comme étape de prétraitement dans des stratégies composées. En particulier, son application est suivie de la règle majorité (la règle 232 dans la classification de Wolfram). La règle de majorité est une règle d'automate cellulaire unidimensionnel très simple et intuitive. À chaque étape, une cellule prend la valeur qui est majoritaire dans son voisinage immédiat, la cellule elle-même et ses deux voisines directes. La figure 1.2 représente deux diagrammes espace-temps de la règle 232.
<figure><img src="image_4.png" /><figcaption>FIGURE 1.2 – Diagrammes espace-temps de la règle 232. Les carrés blancs et noirs représentent les états 1 et 0 respectivement.</figcaption></figure>

La combinaison des deux règles permet d'obtenir un comportement approchant la solution idéale sur un grand ensemble de configurations. Ainsi, la règle 184 illustre parfaitement comment une règle locale, bien que simple et imparfaite, peut jouer un rôle fondamental dans l'émergence d'un comportement global pertinent à partir d'interactions élémentaires. La figure 1.7 illustre l'évolution d'une configuration initiale binaire sous l'action combinée de la règle traffic (184) et de la règle de majorité (232), appliquées successivement (5 itérations chacune) afin d'approcher la classification de la densité. Cette approche est due à Fatès [5], en utilisant les deux règles, traffic et majorité, a présenté un automate cellulaire rendant l'erreur d'approximation du problème de la classification de la densité aussi petit que l'on veut. L'automate cellulaire ainsi présenté est stochastique : chaque cellule applique la règle traffic avec une *p* et la règle majorité avec une probabilité (1 − *p*) [5].

<figure><img src="image_5.png" /><figcaption>FIGURE 1.3 – Application successive des règles traffic et majorité où chaque règle est appliquée dans un cycle de 10 itérations. Les carrés blancs et noirs représentent les états 1 et 0 respectivement.</figcaption></figure>

Ainsi, le problème de la classification de la densité illustre à la fois les ambitions et les limites des systèmes auto-stabilisants : si une forme de stabilisation est toujours possible, la correction vers une décision globalement optimale exige parfois des compromis sur le plan de la localité, du déterminisme, ou du nombre d'états. Ce constat ouvre la voie à des stratégies hybrides ou probabilistes, où l'auto-stabilisation est renforcée par des mécanismes d'auto-correction collective. Cependant, l'auto-stabilisation ne traite pas uniquement les fautes permanentes, ni la manière dont un système peut retrouver un état valide, mais il s'agit de, *corriger* de manière active les erreurs qui surviennent localement. C'est dans ce contexte que s'inscrit la notion d'auto-correction, notamment lorsqu'elle est modélisée à l'aide d'automates cellulaires.
## 1.3 Auto-correction par automates cellulaires

L'auto-correction par automates cellulaires se traduit en un problème de coloriage où état sain désigne toute cellule n'ayant aucune autre cellule adjacente de la même couleur que la cellule considérée. Dans ce contexte, un coloriage désigne une affectation de couleurs à chaque cellule d'une grille discrète (souvent $Z^2$), sous des contraintes locales, deux cellules adjacentes ont deux couleurs différentes. Ces contraintes prennent la forme d'un ensemble de motifs interdits : une configuration est valide si aucun des motifs interdits n'apparaît dans ses voisinages. Un tel ensemble de configurations constitue ce qu'on appelle dans la dynamique symbolique un sous-décalage de type fini (SFT).

Ce problème de coloriage, appelé parfois problème du domino en dimension 2, a été étudié dès les années 1960 par Berger [1], qui a démontré qu'il est indécidable de déterminer, à partir d'un ensemble fini de contraintes locales, s'il existe un coloriage global valide de la grille infinie. Cette indécidabilité marque une limite fondamentale dans l'analyse automatique des systèmes régis par des règles locales. Ainsi, l'étude conjointe de l'auto-correction par automate cellulaire et du problème des coloriages permet de modéliser des mécanismes de correction d'erreurs dans un cadre entièrement local. C'est aussi le cas des pavages. L'idée alors est de concevoir des règles locales pour les automates qui, même si une perturbation ou un changement imprévu affecte l'état des cellules, permettraient au système de revenir à un état stable où les règles de coloriage étaient respectées. Plus précisément, un automate cellulaire est auto-correcteur si les deux conditions suivantes sont vérifiées :

a. Toute configuration saine est fixe sous les itérations de l'automate.

b. Toute grille ayant un nombre fini de cellules perturbées finira par atteindre une configuration entièrement saine en un temps fini.

Divers types de perturbations pourront être considérés. En effet, on peut supposer que des perturbations auront lieu à chaque pas de temps [12] ou simplement supposer que les erreurs sont considérées dans les conditions initiales [11]. Dans le contexte de notre travail, on se place dans le deuxième type d'erreur où, en partant d'une configuration à perturbation finie, sera-t-il possible de générer un automate cellulaire la rendant stable. Ce mécanisme de correction pourra éventuellement modifier ou affecter des cellules initialement saines, pourvu qu'il garantisse la convergence vers un état totalement indemne en un temps fini.

### 1.3.1 État de l'art des coloriages par automates cellulaires

Fatès, Marcovici et Taati dans leur travail [6] ont traité le problème des coloriages par automates cellulaires en ayant $k$ couleurs dans une grille infinie de $Z^2$, les auteurs ont démontré que le cas où $k = 2$ ou $k = 4$ ou $k \ge 5$ sont affirmatifs. i.e. Il existe bien des automates cellulaires permettant de corriger et de stabiliser toute configuration contenant un nombre fini de cellules perturbées.

#### 2-coloriages

La simplicité du problème des 2-coloriages provient du fait qu'il admet une unique configuration valide qui est un damier. La règle directionnelle suivante, similaire à la règle majorité de Toom [19, 27], permet à toute perturbation finie d'être corrigée en un damier. On désigne par $(e_1, e_2)$ la base canonique de $Z^2$.

$$ \forall c \in \mathbb{Z}^2, F(x)_c = \begin{cases} 1 - x_c & \text{si } x_c = x_{c+e_1} = x_{c+e_2}, \\ x_c & \text{sinon.} \end{cases} $$

L'automate cellulaire F donné, fait la distinction entre ses cellules nord et est. Dans ce contexte déterministe, Pippenger a démontré que le fait de considérer toutes les symétries de la règle locale conduit à des résultats négatifs [21]. Une solution isotrope a été donnée en se reposant sur des
<figure><img src="image_6.png" /><figcaption>FIGURE 1.4 – Évolution de l'automate cellulaire pour l'auto-correction des 2-coloriages. Les cellules jaunes sont des cellules en erreur. Les cellules blanches et noires représentent les états 0 et 1 respectivement.</figcaption></figure>

automates cellulaires probabilistes. L'idée est d'appliquer la règle minorité avec une probabilité $\alpha$ et de rester inchangé avec une probabilité $1 - \alpha$ sur un voisinage de von Neuman de rayon 1.

### k-coloriages où $k \ge 5$

Étant donné que toute cellule dans une grille de $\mathbb{Z}^2$ admet quatre cellules qui lui sont adjacentes. Le problème de coloriage pour un nombre de couleurs qui est supérieure ou égale à cinq devient donc plus simple. Il est suffisant de considérer une règle locale qui associe toute cellule en erreur avec une couleur qui n'apparaît pas dans son voisinage de von Neuman. Un tel choix est possible vu le nombre de couleur disponibles. Un tel processus peut être adapté pour des automates déterministes et directionnels ou des automates cellulaires probabilistes et isotropes [6].

<figure><img src="image_7.png" /><figcaption>FIGURE 1.5 – Evolution déterministe de l'automate cellulaire pour l'auto-correction des 5-coloriages. Les cellules jaunes sont des cellules en erreurs.</figcaption></figure>

### 4-coloriages

Le coloriage d'une grille ayant quatre couleurs est plus délicat que les deux cas précédents. Aucune des approches vue n'est applicable pour $k = 4$. Malgré la non trivialité du problème, les auteurs de [6] ont présenté une règle locale directionnelle solvant le problème. Le principe du raisonnement réside dans le lemme suivant :

**Lemme 1** Pour tout choix $(a, b, c, d, e, f, g, h) \in \mathcal{A}^8$ de symboles entourant un carré de taille $2 \times 2$, voir le motif à droite, il existe un choix pour les valeurs des cellules $(\alpha, \beta, \gamma, \sigma) \in \mathcal{A}^4$, rendant ce carré $2 \times 2$ sans erreurs.

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

En utilisant la fonction $\Phi: \mathcal{A}^8 \to \mathcal{A}^4$ qui permet de corriger tout quadruplet $(\alpha, \beta, \gamma, \sigma)$ en se basant sur les valeurs de $(a, b, c, d, e, f, g, h)$ comme présenté dans le lemme 1, on désigne un automate cellulaire qui applique la fonction $\Phi$ sur toute cellule erronée dont la valeur est égale à
la valeur de sa cellule nord ou est et que ses cellules nord, est, nord-est et nord-ouest sont saines. Une illustration des cellules concernées par les corrections est donnée dans la figure 1.6a. La figure 1.6b montre le processus de correction qui se fait au niveau des diagonales et qui diminuent au long des application de $\Phi$. Voir [6] pour plus de détails.

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

(a) La valeur de la cellule en gris est égale à la valeur de sa cellule nord ou est. Les cellules vertes sont toutes des cellules admettant des valeurs différentes de leurs cellules nord et est.

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

(b) Correction d'une diagonale par $\Phi$.

<caption>FIGURE 1.6 – Automate cellulaire déterministe, directionnel résolvant le problème des 4-coloriages.</caption>

• **L'isotropie dans les 4-coloriages** : Trouver une règle locale isotrope pour un automate cellulaire auto-correcteur des 4-coloriages ne manque pas difficultés. Une règle locale été présentée consistante à garder toute cellule saine fixe et de considérer l'ensemble $G = \{q_N, q_S, q_E, q_O\}$ qui représente la valeur des cellules qui constituent le voisinage de von Neuman d'une cellule donnée. Alors toute cellule erronée est échangée en une valeur de $\{0, 1, 2, 3\} \setminus G$ quand ce dernier est non vide, sinon, la cellule considérée prend une valeur aléatoire, uniforme dans l'ensemble $\{0, 1, 2, 3\}$ [6]. L'application de cet automate cellulaire a démontré des simulations positives sous des mises à jours complètement asynchrones [14]. Où, l'asynchronisme dans les mises à jour d'un automate cellulaire consiste à choisir aléatoirement un certain nombre de cellules auxquelles la règle locale sera appliquée. La figure 1.7 représente un exemple de simulation de l'automate cellulaire F.

**Conjecture 1** *Soit F l'automate cellulaire probabiliste, isotrope présenté ci-dessous pour les 4-coloriages. On conjecture que toute configuration perturbée pour les 4-coloriages est corrigée par F presque sûrement.*

<figure><img src="image_11.png" /><figcaption>FIGURE 1.7 – Evolution probabiliste, 1/2-asynchrone de l'automate cellulaire pour l'auto-correction des 4-coloriages. Les cellules jaunes sont des cellules en erreur. Toute couleur correspond à un état dans $\{0, 1, 2, 3\}$.</figcaption></figure>

### 1.3.2 Cas des 3- coloriages

Le fait de se placer dans un alphabet de cardinalité 3 rend le problème de l'auto-correction par automate cellulaire assez complexe et fait qu'aucune des approches précédentes ne pourra
être appliquée. La figure 1.8b nous donne une illustration simple du cas où une grille définie sur l'alphabet $\{0, 1, 2\}$ supposée correcte sauf en deux cellules nous force à orienter l'erreur vers l'extérieur et perturber de nouvelles cellules dans l'espoir de pouvoir à se ramener à une correction possible. Cela montre que peu importe la taille du carré dont l'ensemble des cellules perturbées est contenu, on pourra souvent trouver un motif (pattern) qui nécessitera des informations supplémentaires qui soient en dehors du carré pris au départ avant de procéder à tout type de correction.

<figure><img src="image_12.png" /><figcaption>(a) Un pattern valide et ces flèches correspondantes.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) Auto-correction locale non possible.</figcaption></figure>

FIGURE 1.8 – Exemples de motifs pour les 3- coloriages.

## Modèle des six sommets

Marcovici a présenté un modèle séquentiel défini avec des symboles additionnels qui permet de caractériser les motifs admissibles pour les 3-coloriages. La méthode considérée est la suivante : soient deux entiers $p, q \in \{0, 1, 2\}$ tel que $p \neq q$ on a soit $q = (p + 1) \mod 3$ ou bien $q = (p - 1) \mod 3$. Alors, suivant les cas, on trace entre deux cellules saine de $\mathbb{Z}^2$ qui sont horizontalement adjacentes et ayant pour valeurs $p, q$ respectivement une flèche qui soit orientée vers le haut si $q = p + 1 \mod 3$, sinon la flèche sera orientée vers le bas (voir la figure 1.8a pour un exemple). De la même façon, on définit sur les bordes de deux cellules correctes verticalement adjacentes ayant pour valeurs $p, q$ respectivement une flèche qui soit orientée vers la droite si $q = p + 1 \mod 3$ sinon vers la gauche.

L'association des flèches permet la caractériser des patterns sains. En effet, chaque cellule saine admet exactement deux flèches entrantes et deux flèches sortantes. En considérant un carré quelconque d'une taille donnée, le motif le constituant est admissible (voir la figure 1.9a) si :

a. L'ensemble de tous les chemins formés par la combinaison des flèches associées au carré ne se croisent pas.

b. Le nombre de chemins entrants est égal au nombre de chemins sortants. Les entrées du carré sont supposées être ses côtés nord et ouest et les sorties sont ses côtés est et sud.

Avec une telle approche, on peut simplement se limiter au repérage des flèches ayant pour direction sud et est et aux chemins qu'elles constituent.

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

Notons que dans certains cas, voir la figure 1.9b, le nombre de chemins qu'un motif contient est bien supérieur au nombre de chemins qui relient les entrées et les sorties du motif.

Ce modèle, appelé *modèle des six sommets*, n'est pas toujours applicable à tout carré de côté L. En effet, certains motifs de taille $L \times L$ ne peuvent pas être corrigés tout en conservant les bordures initiales du carré. Dans de tels cas, il est nécessaire d'augmenter la taille du carré d'une unité, c'est-à-dire de considérer une longueur $L + 1$ au lieu de L. Ce modèle constitue une étape importante vers la correction d'un 3-coloriage au moyen d'un automate cellulaire. Toutefois, il présente deux limites principales : un temps de résolution élevé et la nécessité d'ajouter des symboles supplémentaires à l'alphabet $\{0, 1, 2\}$. À ce jour, aucune définition rigoureuse d'un tel automate n'a encore été établie.
<figure><img src="image_15.png" /><figcaption>FIGURE 1.9 – Modèle des six sommets.</figcaption></figure>

Complexité des 3–coloriages

Une question naturelle se pose derrière ce qui rend le problème des 3-coloriages aussi com-
plexe. Cela consiste à se demander ou à cherche l'existence d'un comportement additionnel spé-
cifique qui apparaît uniquement quand la taille de l'alphabet est de 3 et qui ne se présente pas
dans les autres cas.

Afin de donner une réponse à notre question, nous commençons par attirer l'attention sur les
automates auto-correcteurs définis précédemment sur des alphabets de taille différente de 3.
En effet, si $k \ge 5$ alors toute cellule erronée dispose d'au moins d'une lettre de l'alphabet qui lui soit
différente et avec quoi l'erreur se corrigera. Cela associe chaque erreur locale avec une correction
locale qui à son application aucune perturbation supplémentaire ne sera rajoutée à l'ensemble
des perturbations initiales. Le cas $k = 2$ est trivial vu que le damier est la seule possibilité. Mais
pour le $k = 2$, on constate que le fait de rajouter ou de ne pas rajouter des erreurs au long des
itérations n'est pas important pourvu qu'à chaque pas de temps l'ensemble des perturbations est
inclus dans un carré corrigible. Un carré corrigible est un carré qui en dehors du processus de
correction, on peut l'associe avec des états sains.

Ce n'est donc pas difficile de constater que le cas $k = 3$ pourra facilement violer au moins l'un des deux comportements suivants :

1. L'ensemble des erreurs est contenu dans un carré corrigible.

2. Il y a une correction qui ne génère pas de nouvelle perturbation au fil du temps.

Pour cela, il est très important de rappeler la position de notre travail, laquelle consiste à cher-
cher un automate cellulaire qui corrige une configuration que l'on a perturbée. i.e, en perturbant
une configuration saine, sera-t-il possible de la corriger par un automate cellulaire ?

De ce fait, dès lors qu'un automate cellulaire, en corrigeant sur un alphabet de taille 3, en-
gendre de nouvelles perturbations, il peut être entraîné dans une succession infinie de corrections,
même si les perturbations initiales étaient confinées dans des carrés corrigibles. Ceci ne peut être
dévité que si les perturbations nouvellement créées ne sont pas anarchiques, mais au contraire
*contrôlées*, de sorte que chacune d'elles n'engendre pas une chaîne infinie de nouvelles erreurs à
corriger.

L'automate cellulaire qui nous approchera le mieux de la solution de notre problème est ce-
lui qui ne générera pas d'erreurs supplémentaires au fil des itérations et tel qu'à chaque itération
l'existence d'une correction devra être garantie. Une autre correction pourra être visualisée en se
permettant d'élargir la taille de l'alphabet initial. Elle consiste à rajouter des nouveaux symboles
à l'alphabet avec l'objectif de minimiser les erreurs d'une itération à l'autre. Les symboles additionnels doivent être éliminés par le même automate cellulaire qui les a fait apparaître à partir d'une configuration perturbée de {0, 1, 2}. Ils doivent être considérés comme des marqueurs temporaires, servant d'outil intermédiaire pour guider l'évolution de l'automate tout en conservant une trace de l'origine des erreurs. Leur disparition finale permet alors à l'automate de stabiliser toute configuration initialement erronée.

**Question 1** Comment se fait-il que l'on puisse corriger un 3-coloriage en ajoutant des symboles supplémentaires, mais que le problème reste tout aussi difficile lorsque l'on se restreint à un alphabet de taille 3 ? Qu'est-ce qui rend le passage de l'un à l'autre non trivial ?

**Question 2** Quel est le nombre minimal de symboles nécessaires pour qu'un automate cellulaire puisse corriger efficacement un 3-coloriage ?

## 1.4 Auto-stabilisation sous perturbations permanentes

Dans l'étude des systèmes distribués, la question de la résilience aux perturbations constitue un enjeu central. Plus spécifiquement, dans les modèles discrets comme les automates cellulaires (AC), elle prend une dimension particulièrement complexe lorsqu'on considère non pas des erreurs ponctuelles, mais des perturbations permanentes, c'est-à-dire des altérations susceptibles de survenir à chaque pas de temps. Ces perturbations, qu'elles soient aléatoires ou déterministes, mettent à l'épreuve la capacité du système à maintenir ou retrouver un comportement globalement stable.

Contrairement au cadre classique de l'auto-stabilisation, dans lequel le système part d'un état arbitrairement corrompu mais n'est plus perturbé par la suite, le cas des perturbations récurrentes impose une contrainte bien plus forte. Il ne s'agit plus simplement de converger vers un état correct, mais de lutter continuellement contre le bruit, et de préserver, malgré celui-ci, une forme de régularité ou de cohérence à l'échelle globale.

Les travaux pionniers dans ce domaine sont ceux de Peter Gács [10], qui a démontré en 2001 qu'il est théoriquement possible de construire un automate cellulaire unidimensionnel fiable, capable de maintenir un comportement correct malgré l'injection d'erreurs aléatoires à chaque pas de temps. Sa construction repose sur une architecture hiérarchique extrêmement sophistiquée, dans laquelle des mécanismes de correction d'erreurs sont imbriqués à plusieurs échelles, permettant à des structures locales de détecter, corriger, et reconstruire l'information de manière entièrement distribuée. Ce résultat constitue à ce jour l'un des rares exemples d'un AC robuste aux perturbations permanentes dans un cadre stochastique.

Dans une autre direction, les travaux autour de la règle de Toom, appliquée principalement aux AC bidimensionnels, ont montré qu'une certaine asymétrie dans les règles locales, notamment dans les modèles de vote majoritaire, peut suffire à garantir la stabilité d'un état global face à des erreurs répétées. Cette approche offre une alternative plus simple et géométrique, quoique moins générale, à la correction d'erreurs hiérarchique de Gács [10]. Elle a permis de mieux comprendre comment des mécanismes de redondance spatiale pouvaient naturellement émerger dans des systèmes locaux.

Ces différentes approches, bien que différentes dans leurs méthodes et leurs objectifs, convergent toutes vers une même intuition : sous certaines conditions structurelles, un automate cellulaire peut développer une forme d'auto-organisation robuste, capable de filtrer l'erreur au fil du temps.

## 1.5 Organisation du Rapport

Ce rapport est structuré en trois chapitres, chacun correspondant à une étape précise de notre étude des automates cellulaires appliqués aux problèmes de coloriage sur le réseau $Z^2$.
* Le chapitre 1 est consacré à l'analyse théorique du problème du 3-coloriage. On commence par introduire les concepts fondamentaux nécessaires à la compréhension des automates cellulaires, en particulier dans le contexte du coloriage. Une attention particulière sera portée sur le problème du 3-coloriage, pour lequel il n'existe à ce jour aucune solution connue par automate cellulaire en temps fini. Nous avons identifié des configurations dites uniquement corrigibles, étudié leurs comportements dynamiques, et dégagé certaines propriétés que devrait vérifier un automate cellulaire s'il était capable de résoudre ce problème. Ce chapitre constitue la base conceptuelle de notre travail.

* Le chapitre 2 présente la construction d'un automate cellulaire conçu pour corriger partiellement les erreurs dans le cadre des 3-coloriages. L'approche adoptée repose sur un processus de correction dirigé vers le nord et l'est, ainsi que sur la reconnaissance de motifs locaux de taille 3 × 3 permettant de bloquer ou rediriger les erreurs. Nous allons montrer que cet automate permet de corriger la grande majorité des perturbations en un temps fini, et identifier trois types d'erreurs qui peuvent subsister (nord-est, nord, est). On formule également deux grandes questions autour des limites de correction : (1) jusqu'à quel point peut-on corriger des configurations perturbées ? et (2) est-il possible de concevoir un automate qui diminue systématiquement le nombre d'erreurs au cours des itérations ? Ce chapitre offre une réponse partielle au problème des 3-coloriages, en s'attaquant à une version plus faible du problème

* Le chapitre 3 ouvre la réflexion sur le cas des 4-coloriages. On commence par l'analyse d'une règle probabiliste proposée par Fatès, Marcovici et Tati dans [6], en identifiant certains éléments clés montrant qu'elle permet, dans certaines situations, de corriger les erreurs. Ce travail reste cependant en cours : on sera limité ici à une première exploration, en posant les bases pour des analyses plus approfondies à venir. L'objectif de ce chapitre est donc de tracer une piste vers l'étude de l'approches probabiliste performante pour la correction non directionnelle des 4-coloriages par AC.
# Chapitre 2

# Coloriages par Automates Cellulaires

Nous ne pouvons voir que l'avenir proche, mais nous savons déjà qu'il y a beaucoup à faire.

Alan Turing.
(1950).

Notre travail se situe dans le contexte des automates cellulaires (AC) en dimension 2. L'objectif de ce chapitre est la présentation globale des automates cellulaires ainsi que le problème des coloriages et leurs corrections. Nous allons commencer par donner les outils nécessaires en dynamique symbolique pour l'introduction de notre travail. Ensuite, nous aborderons les notions de base des coloriages par automates cellulaires déterministes. Nous finirons par nous concentrer sur le problème des 3-coloriages où nous allons mettre en lumière quelques propriétés et obstacles qui favorisent et défavorisent, à la fois, la possibilité d'une correction des 3-coloriages par AC.

## 2.1 Notions fondamentales de la dynamique symbolique

Dans cette section, nous regroupons les différentes notions de dynamique symbolique dont nous aurons besoin pour la suite.

### Notation 1

* L'alphabet $\mathcal{A}$ est un ensemble fini de symboles.

* L'espace symbolique $\mathcal{A}^{\mathbb{Z}^2}$ (espace des configurations) est l'espace de toutes les configurations sur $\mathbb{Z}^2$ qu'on peut construire à partir de l'alphabet $\mathcal{A}$. Dans le cas où $d = 1$, l'espace des configurations $\mathcal{A}^{\mathbb{Z}}$ est représenté par toutes les suites bi-infinies d'éléments de $\mathcal{A}$.

* Un motif u de $\mathcal{A}^{d_1 \times d_2}$ est un bloc fini d'éléments de $\mathcal{A}$ de taille $|u| = d_1 \times d_2$.

* Un motif u est un sous-motif de v et on écrit $u \subset v$, si v contient u. Exemple : si $d = 1$ et $\mathcal{A} = \{0,1\}$ alors $u = 01$ est un sous-motif de v = 1001.

* Soit $u \in \mathcal{A}^{1 \times n}$ et $v \in \mathcal{A}^{1 \times m}$, la concaténation des deux motifs u et v est le motif $uv \in \mathcal{A}^{1 \times (n+m)}$.

* Soit $i \in \mathbb{Z}^d$, l'élément $u_i \in \mathcal{A}$ désigne l'état du motif u qui est en position i.

* On munit l'espace $\mathcal{A}^{\mathbb{Z}^d}$ d'une distance $D : \mathcal{A}^{\mathbb{Z}^d} \to \mathbb{R}$ définie comme suit :

$$ \begin{cases} D(x, y) = 2^{-\min\{\|\vec{i}\|:x_i \neq y_i\}} & \text{où } \|\vec{i}\| = \max_{s=\{1, \dots, d\}} \{|i_s|\} \text{ pour tout } x \neq y \in \mathcal{A}^{\mathbb{Z}^d}. \\ D(x, y) = 0 & \text{si } x = y. \end{cases} $$
**Example 1** La distance D entre deux configurations x et y, qui partagent les mêmes états au niveau du carré central de longueur k ∈ N, avec une différence dans l'une des cellules située à une distance de k + 1 par rapport à l'origine, est donnée par 2^{-(k+1)}.

### 2.1.1 Automates cellulaires

**Définition 1 (Automate cellulaire déterministe)** Un automate cellulaire est un quadruplet $\mathcal{F} = (\mathcal{G}, \mathcal{V}, \mathcal{A}, f)$ où

* $\mathcal{G} = \mathbb{Z}^2$, avec $d \in \mathbb{N}^*$ est l'ensemble des cellules,

* $\mathcal{V} = \{v_1, \dots, v_{|\mathcal{V}|}\}$ est un ensemble fini de vecteur de $\mathcal{G}$ formant le voisinage,

* $\mathcal{A}$ est un ensemble fini d'état dit l'alphabet,

* $f: \mathcal{A}^{|\mathcal{V}|} \to \mathcal{A}$ est la règle de transition locale.

**Les configurations** : une configuration $c$ de l'automate cellulaire $\mathcal{F}$ est l'affectation de chaque cellule $i \in \mathcal{G}$ à un état $c(i) \in \mathcal{A}$. On écrit $c \in \mathcal{A}^\mathcal{G}$. Étant donnée une configuration $c_0$, l'application synchrone et uniforme de la règle de transition locale définit une nouvelle configuration $c_1$ par

$$c_1(i) = f(c_0(i + v_1), \dots, c_0(i + v_{|\mathcal{V}|})).$$

**La fonction globale** : on appelle fonction globale cette action de l'automate cellulaire sur les configurations.

**Diagramme espace-temps** : Le diagramme espace-temps d'un automate cellulaire est une représentation graphique de l'évolution d'un système au fil du temps. Chaque ligne horizontale du diagramme correspond à l'état de l'ensemble des cellules à un instant $t \in \mathbb{N}$ donné, et chaque ligne successive montre cet état à un instant $t+1$. Dans ce travail, on considère une évolution du temps du haut en bas. Cette approche permet de suivre l'évolution des configurations. C'est un outil fondamental pour visualiser le comportement global d'un automate cellulaire à partir de règles locales simples.

**Example 2 (L'AC de décalage en D1)** Soit $\mathcal{A} = \{0, 1\}$ et $\mathcal{V} = \{0, 1\}$. L'automate cellulaire du décalage $\sigma: \mathcal{A}^\mathbb{Z} \to \mathcal{A}^\mathbb{Z}$ est défini par $\forall x \in \mathbb{Z}: \sigma(x)_i = x_{i+1}$. La figure 2.1 représente le diagramme espace-temps du décalage où le temps va du haut vers le bas.

<figure><img src="image_16.png" /><figcaption>FIGURE 2.1 – Diagramme espace temps du décalage. Les cellules blanches représentent l'état 0 et les cellules noires représentent l'état 1.</figcaption></figure>

**Voisinage en 2D** : les deux voisinages les plus utilisés dans le cadre des automates cellulaires définis sur $\mathcal{G} = \mathbb{Z}^2$ sont les suivants :

* von Neumman :

$$\mathcal{V}_N = \{(0,0); (0,1); (0,-1); (1,0); (-1,0)\};$$

* Moore :

$$\mathcal{V}_M = \{(0,0); (0,1); (0,-1); (1,0); (-1,0); (1,1); (-1,1); (-1,-1); (1,-1)\};$$
<figure><img src="image_17.png" /><figcaption>(a) Voisinage de von Neuman</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>(b) Voisinage de Moore</figcaption></figure>

## 2.2 Coloriages par automates cellulaires

L'objectif de cette section est l'introduction des différentes notions et notations qui seront utilisées dans le cadre des coloriages par automates cellulaires.

**Notation 2** Soient l'alphabet $\mathcal{A}$ avec $|\mathcal{A}| = k$ et $x, y$ deux configurations de $\mathcal{A}^{\mathbb{Z}^2}$.

* L'ensemble des positions auxquelles les états de $x$ sont différents de ceux de $y$ est noté :

$$ \Delta(x, y) = \{i \in \mathbb{Z}^2 : x_i \neq y_i\}. $$

* On dit que $x$ est une configuration légale si elle satisfait la condition des $k$-coloriages. Autrement dit, si deux cellules adjacentes quelconques de $x$ sont associées à deux états différents dans $\mathcal{A}$.

* On dit que la configuration $y$ est une perturbation finie de $x$ si l'ensemble $\Delta(x, y)$ est fini.

* On appelle par la correction d'une configuration le fait de restabiliser ou de transformer une configuration perturbée en une configuration saine.

Notons par $V, \tilde{V}$ respectivement l'ensemble des configurations légales et l'ensemble des perturbations finies pour les $k$-coloriages définis sur $\mathcal{A}^{\mathbb{Z}^2}$.

**Définition 2 (Auto-correction par un AC déterministe)** Un automate cellulaire $F$ est dit auto-correcteur des $k$-coloriages s'il satisfait les conditions suivantes :

1. Toute configuration $x \in V$ est fixe sous les itérations de $F$, i.e., $\forall x \in V, F(x) = x$.

2. Toute configuration $y \in \tilde{V}$ converge vers une configuration de $V$ en un temps fini, i.e.,

$$ \forall y \in \tilde{V}, \exists n \in \mathbb{N} : F^n(y) \in V. $$

## 2.3 Existence de solution pour les 3-coloriages

Not all errors are meant to be corrected.

Pensée personnelle.

Dans cette section, on s'intéresse au problème des 3-coloriages dans laquelle on présente les différentes propriétés nécessaires pour une correction ou une non-existence d'une correction du problème des 3-coloriages par AC. L'objectif principal est de souligner les obstacles rencontrés dans notre analyse et de discuter des résultats, qui montrent à la fois des éléments en faveur d'une solution et d'autres qui suggèrent qu'aucune solution n'existe.

**Notation 3**

* L'ensemble de toutes les perturbations issues d'une configuration $x \in V$ est désigné par $\Theta(x)$.

* L'ensemble de toutes les configurations dans $V$ qui corrigent un ou des éléments de $\Theta(x)$ est noté par $\tilde{\chi}(x)$, autrement dit, $\tilde{\chi}(x) = \{z \in V : \exists y \in \Theta(x) \text{ tel que } z \text{ corrige y}\}$.

* Une configuration $x \in V$ est dite uniquement corrigible si $\tilde{\chi}(x) = \{x\}$, i.e. la configuration $x$ est uniquement corrigible si elle est l'unique configuration dans $V$ qui corrige tout élément de $\Theta(x)$.
### 2.3.1 Des configurations uniquement corrigibles

On donne dans cette partie un exemple des configurations uniquement corrigibles pour les 3-coloriages. La caractérisation complète de ces configurations n'est pas envisagée ici. En effet, on s'intéresse uniquement aux configurations utiles pour la suite de notre travail.

**Proposition 1** *Toute configuration $x \in V$ qui satisfait les propriétés suivantes est uniquement corrigible :*

1. Toute ligne $j \in \mathbb{Z}$ de $x$ satisfait pour tout $i \in \mathbb{Z}$ :

$$x_{(i,j)} = x_{(i+3,j)} \text{ et } x_{(i+1,j)} \neq x_{(i+2,j)} \text{ et } x_{(i,j)} \neq x_{(i+1,j)} \text{ et } x_{(i,j)} \neq x_{(i+2,j)}$$

2. $x$ satisfait une et une seule des équations suivantes :

$$\forall (i, j) \in \mathbb{Z}^2, x_{(i,j)} = x_{(i-1, j+1)} \text{ ou } \forall (i, j) \in \mathbb{Z}^2, x_{(i,j)} = x_{(i-1, j-1)}$$

**Remarque 1** *La condition (1) de la proposition 1 est équivalente au fait que toute ligne $j \in \mathbb{Z}$ de $x$ est la concaténation infinie de l'un des motifs suivants :* $210, 201 \in \mathcal{A}^{1 \times 3}$.

**Preuve.** Soit $x$ une configuration saine de $\mathcal{A}^{\mathbb{Z}^2}$ telle que toute ligne de $x$ est une concaténation infinie du motif $201 \in \mathcal{A}^3$. De plus, on suppose que $\forall (i, j) \in \mathbb{Z}^2$, on a $x_{(i,j)} = x_{(i-1,j+1)}$ (voir la figure 2.3a). Soit $y$ un élément de $\Theta(x)$. Sans perte de généralité, on suppose que les perturbations de la configuration $y$ sont contenues dans un motif P de taille $n \times n$ avec $n \in \mathbb{N}$ quelconque, i.e, en dehors de ce motif la configuration $y$ coïncide avec la configuration $x$. (voir la figure 2.3b). Le sous-motif perturbé P de $y$ de taille $n \times n$, supposé centré, satisfait les propriétés suivantes : (1) Les cellules ouest et sud de sa cellule en position (0,0) sont égales. (2) Les cellules ouest et nord de sa cellule en position (0, $n-1$) sont différentes.

<figure><img src="image_19.png" /><figcaption>(a) Un sous-motif de $x$.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(b) La configuration $y$.</figcaption></figure>

**FIGURE 2.3** – Élément de preuve. Le carré blanc représente la partie perturbée de $y$ centré par rapport au repère.

Démontrons que l'unique motif qui peut remplacer le motif perturbé P corrige la configuration $y$ en $x$ (suivre avec la figure 2.3b pour un exemple). La preuve sera faite en affectant chaque cellule perturbée avec l'unique valeur de $\mathcal{A}$ qui la corrige. L'affectation sera par ordre des colonnes où chaque colonne est corrigée en commençant par ses cellules d'en haut jusqu'à la dernière cellule du bas.

Par la propriété (2) vérifiée par le motif perturbé P annoncée ci-dessus, la cellule en position $(0, n-1)$ ne peut être associée qu'à un seul état dans $\mathcal{A}$ qui la rend saine. De plus, $y_{(-1,n)} = y_{(0,n-1)}$. La notation $y_{(i,j)}$ désigne l'unique état dans $\mathcal{A}$ qui corrige la cellule en position $(i, j) \in \mathbb{Z}^2$ de $y$. Regardons la cellule en position $(0, n-2)$, on a $y_{(0,n-1)} \neq y_{(-1,n-2)}$. En effet, considérons une cellule saine de $x$ que l'on suppose en position $(0,0)$. Cette dernière vérifie $x_{(0,1)} = x_{(-1,-1)}$. Comme $\forall (i,j) \in [0, n-1] \times [0, n-1]$ avec $(i,j) \in \mathbb{Z}^2$, on a $x_{(i,j)} = y_{(i,j)}$ on conclut donc qu'il existe une seule valeur dans $\mathcal{A}$ qui rend la cellule en position $(0, n-2)$ saine. De plus, $y_{(-1,n-1)} = y_{(0,n-2)}$. En généralisant cet argument sur toutes les cellules en position $(0, j)$ avec $0 < j \leq n-1$, en déduit que
la première colonne de P est corrigée d'une façon unique et que $y_{(0,j)} = x_{(0,j)}, \forall 0 < j \le n-1$. La correction de la cellule (0,0) est assurée par la propriété (1) annoncée ci-dessus.

Appliquant par récurrence les mêmes arguments sur les prochaines colonnes par ordre. Considérons la colonne $j \in \mathbb{N}$ avec $j \in [0, n-1]$. On suppose que pour tout $i \in [0, n]$, $x_{(j-1,i)} = y_{(j-1,i)}$. D'où $y_{(j,n)} \neq y_{(j-1,n-1)}$ et donc la cellule en position $(j, n-1)$ admet une seule valeur dans $\mathcal{A}$ la rendant correcte. De plus, $y_{(j,n-1)} = y_{(j-1,n)}$ et $y_{(j,n-1)} \neq y_{(j-1,n-2)}$. Par le même raisonnement qu'avec la colonne 0, on déduit que la configuration $x$ est uniquement corrigible. Les autres cas se déduisent en utilisant les mêmes arguments. ■

**Notation 4** Pour la suite de ce chapitre, on suppose que toute configuration auto-corrigible qui satisfait l'équation $\forall (i, j) \in \mathbb{Z}^2, x_{(i,j)} = x_{(i-1,j-1)}$ et que chacune de ces lignes est la concaténation infinie du motif 201 est dénotée par $x_D^-$. De même toute configuration qui satisfait $\forall (i, j) \in \mathbb{Z}^2, x_{(i,j)} = x_{(i-1,j+1)}$ et que chacune de ces lignes est la concaténation infinie du motif 201 est dénotée par $x_D^+$.

**Question 3** Existe-t-il d'autres configurations auto-corrigibles différentes des configurations citées dans la proposition 1 ? Peut-on avoir une caractérisation globale pour ces dernières ?

### 2.3.2 Des chemins à complétion obligatoire

Dans cette section, nous mettons en évidence certains motifs rencontrés au cours de notre analyse, qui semblent être à complétion obligatoire. Ces motifs, désignés sous le terme de chemins diagonaux, apparaissent comme des sous-motifs des configurations uniquement corrigibles $x_D^+$ et $x_D^-$ introduites dans la proposition 1. Cependant, cette observation est fondée uniquement sur nos constatations et n'est pas encore appuyée par une preuve théorique.

Soit P un sous-motif de $x_D^+$ de taille $(k+1) \times (k+1)$ avec $k \in \mathbb{N}: k \ge 4$ supposé central, il est immédiat que les cellules en positions $i \in \mathbb{Z}^2: ||i||_\infty = k+1$ se complète soit en des motifs de $x_D^+$ ou de $x_D^-$. Formellement, soit $j \in \mathbb{Z}: -k \le j \le k$. Si $P_{(j,k+1)} = P_{(j+1,k)}$ alors $\forall -k \le i \le j: P_{(i,k+1)} = P_{(i+1,k)}$. De même, si $P_{(j,k+1)} = P_{(j-1,k)}$ alors $\forall j \le i \le k+1: P_{(i,k+1)} = P_{(i-1,k)}$. On appelle la suite de ces motifs des chemins de $x_D^+$ ou de $x_D^-$. On conjecture la propriété suivante :

**Conjecture 2** On conjecture qu'il n'existe pas de configuration saine qui admet un chemin de $x_D^+$ ou de $x_D^-$ avec une entrée infinie et une sortie en boucle (finie).

Autrement dit, soit $x \in V$ une configuration saine. Si $x$ contient un sous-motif P de $x_D^+$ ou de $x_D^-$ de taille $(k+1) \times (k+1)$ avec $k \in \mathbb{N}: k \ge 4$ alors les chemins formés se complètent pour former soit des boucles fermées (voir la figure 2.4) soit des chemins dont leurs entrées et sorties se propagent à l'infini (voir la figure 2.5).

<figure><img src="image_21.png" /><figcaption>FIGURE 2.4 – Chemins formant une boucle.</figcaption></figure>
<figure><img src="image_22.png" /><figcaption>FIGURE 2.5 – Chemins infinis. Les flèches désignent la direction des chemins qui se poursuivent à l'infini.</figcaption></figure>

### 2.3.3 Des perturbations finies non prises en compte dans la correction

Dans cette partie, nous tenons à souligner qu'il existe des configurations contenant un nombre fini de cellules en erreur, mais qui ne semblent pas résulter d'une simple perturbation d'une configuration saine. Cette observation est liée à la nature des chemins à complétion obligatoire identifiés dans la section précédente. En effet, ces chemins doivent, par observation, être soit connectés à l'infini avec une entrée et une sortie infinies, soit former une boucle fermée. Nous avons tenté de construire une configuration saine qui ne corresponde à aucun de ces deux cas, sans y parvenir.

**Conjecture 3** Considérons la configuration $x_D^+$ définie précédemment. Soit $i_0 \in \mathbb{N}$ un nombre impair assez grand et $y \in \mathcal{A}^{\mathbb{Z}^2}$ une configuration qui coïncide avec $x_D^+$ sauf aux positions suivantes :

$$ \begin{cases} \forall p_1 \in \mathbb{N}: 0 \le p_1 \le i_0, y(i_0-p_1+k, p_1+k) = 0, \forall k \in \{0, 1\} \\ \forall p_2 \in \mathbb{N}: 0 \le p_2 \le i_0 - 1, y(i_0-p_2, p_2+1) = 1. \end{cases} $$

Soit $\mathcal{P}_k$ l'ensemble des cellules de $y$ délimitées par les cellules se trouvant aux positions suivantes :

$$ \{(i_0-kr+p, -kr), (i_0+1+kr, -r+p): 0 \le p \le 2kr+1\} \cup \{(i_0-kr, -kr+p), (i_0+1-kr+p, kr+1): 0 \le k \le 2kr\} $$

($\mathcal{P}_1$ est la partie dénotée par zone A dans la figure 2.6 pour $r = 2$ et $i_0 = 17$), alors, il n'existe aucune configuration $z \in \Theta(x)$ avec $x \in \mathbf{V}$ telle que :

$$ \begin{cases} z(i,j) = y(i,j) & \text{si } (i,j) \in \mathcal{P}_1, \\ z(i,j) & \text{si } (i,j) \notin \mathcal{P}_1. \end{cases} $$
<figure><img src="image_23.png" /><figcaption>FIGURE 2.6 – Une perturbation d'une configuration auto-correctrice. Les cellules entourées en rouge sont des cellules en erreur. Le repère est positionné à l'origine (0,0).</figcaption></figure>
On présente dans la figure 2.7 notre tentative de construction d'une configuration qui coïncide avec y sur l'ensemble des cellules $\mathcal{P}_1$ et telle que le reste de ses cellules sont saines. Une infinité de configurations peuvent être construites sous ces conditions mais nous n'avons trouvé aucune configuration qui soit le résultat d'une perturbation finie d'une configuration saine.

<figure><img src="image_24.png" /><figcaption>FIGURE 2.7 – Une configuration admettant trois cellules en erreur mais qui ne semble pas être le résultat d'une perturbation finie d'une configuration saine.</figcaption></figure>

**Proposition 2** Soit $y \in \mathcal{A}^{\mathbb{Z}^2}$ la configuration définie dans la conjecture 3 pour un certain $i_0$ assez grand. La configuration y est représentée dans la figure 2.6. Soit F un automate cellulaire de rayon $r > 0$ associé à une règle locale f. On a les propriétés suivantes :

1. Si les deux ensembles $\mathcal{A}, \mathcal{B}$ suivants sont vides alors F n'est pas une solution pour les 3-coloriages :

$$ \mathcal{A} = \{i \in \text{zone A}: F(x)_i \neq x_i\}; \mathcal{B} = \{i \in \text{zone B}: F(x)_i \neq x_i\}. $$

2. Si F corrige la zone A indépendamment de la zone B ou vice-versa alors F ne résout pas le problème des 3-coloriages en un temps fini.

**Preuve.**

1. C'est évident car si $\mathcal{A} = \emptyset$ et $\mathcal{B} = \emptyset$, alors la configuration perturbée y est fixe.

2. Par l'absurde, supposons que F corrige la zone A indépendamment de la zone B. Sans perte de généralité, on suppose que l'ensemble $\mathcal{B}$ est vide. Alors, il existe un itéré $n_0 \in \mathbb{N}$ et une position $i \in \mathbb{N}$ tels que $\forall k \ge i$ et $\forall j \in \mathbb{Z}$, on a $F^{n_0}(y)_{(k,j)}$ saine. De plus, $F^{n_0}(y)_{(k,j)} = x_D^+(k,j)$ (voir la figure 2.8). Considérons la configuration $z \in \mathcal{A}^{\mathbb{Z}^2}$ qui coïncide avec $x_D^+$ sauf aux positions suivantes :

$$ \begin{cases} \forall p_1 \in \mathbb{Z}: z_{(i_0-p_1+k, p_1+k)} = 0, \forall k \in \{0, 1\} \\ \forall p_2 \in \mathbb{Z}: z_{(i_0-p_2, p_2+1)} = 1. \end{cases} $$

Soit $\tilde{z}$ une perturbation de $z$ qui coincide avec $z$ sauf aux positions suivantes (voir la figure 2.9) :

$$ \begin{cases} \forall p_1 \in \mathbb{N}: 0 \le p_1 \le i_0, y_{(i_0-p_1, p_1)} = 2, \\ \forall p_1 \in \mathbb{N}: 0 \le p_1 \le i_0, y_{(i_0-p_1+1, p_1+1)} = 1, \\ \forall p_2 \in \mathbb{N}: 0 \le p_2 \le i_0 - 1, y_{(i_0-p_2, p_2+1)} = 0. \end{cases} $$

Par conséquent, l'application de F sur la configuration $\tilde{z}$ engendre des corrections infinies.
<figure><img src="image_25.png" /><figcaption>FIGURE 2.8 – La configuration $F^{n_0}(y)$. La zone C représente une zone contenant des erreurs. Sa taille et la nature de ses erreurs dépendent de F et de son rayon.</figcaption></figure>
<figure><img src="image_26.png" /><figcaption>FIGURE 2.9 – La configuration ź.</figcaption></figure>
### 2.3.4 Condition nécessaire pour une correction ternaire

L'objectif de cette section est la présentation de quelques conditions qu'une règle locale devra satisfaire afin de permettre la correction de toute configuration non saine issue d'une perturbation finie d'une configuration saine.

**Notation 5** On dénote par $\mathcal{S}$ l'ensemble des motifs $P \in \mathcal{A}^{(2r+1) \times (2r+1)}$ qui satisfont les conditions suivantes (voir la figure 2.10a) :

1. La cellule centrale de P est supposée en position (0,0).

2. $P_{(0,0)}$ est une cellule erronée.

3. $P_{[-r,r] \times [-r,-1]}$ est un sous-motif de $x_D^+$.

<figure><img src="image_27.png" /><figcaption>(a) Exemple d'un motif P pour $r=2$.</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>(b) Une partie de la configuration x.</figcaption></figure>

**FIGURE 2.10** – Illustration pour la proposition 3. La cellule centrale est encadrée en rouge (la convention est gardée dans la suite).

**Proposition 3** Soit F un automate cellulaire associé à une règle locale $f: \mathcal{A}^{(2r+1) \times (2r+1)} \to \mathcal{A}$ ayant un voisinage de Moore de rayon $r > 0$. Si la règle locale satisfait les conditions suivantes :

a. L'image de tout motif P $\in \mathcal{S}$ par $f$ est différente de $P_{(1,-1)}$.

b. Toute cellule saine est inactive.

alors l'automate cellulaire F ne résout pas le problème des 3-coloriages.

**Preuve.** Soit F un automate cellulaire ayant un voisinage de Moore de rayon $r > 0$. Soit $f$ sa règle locale associée. Considérons la configuration $x$ définie comme suit (voir la figure 2.10b) :

$$ egin{cases} x_{(i,j)} = x_D^+(i,j) & \text{si } (i,j) \neq (0,1) \\ x_{(0,1)} = x_D^+(0,0) = 1. & \end{cases} $$

Supposons que l'image de tout motif P $\in \mathcal{A}^{(2r+1) \times (2r+1)}$ qui satisfait les conditions données en proposition 3 par la règle locale $f$ est différente de $P_{(1,-1)}$. On en déduit, $F(x)_{(0,0)} \in \{0,2\}$ et

$$ \forall (i, j) \in \{\mathbb{Z} \times \}-\infty, -1\} \cup \{[1, \infty \times \{0\}], F(x)_{(i,j)} = x_{(i,j)} \text{ par la condition (b) satisfaite par } f \text{ (voir figure 2.11).} $$

Donc $F(x)_{(0,0)}$ est erronée et les motifs $P = F(x)_{[1-r,1+r] \times [-r,r]}$ si $F(x)_{(0,0)} = 2$ et $P = F(x)_{[-r,r] \times [-1-r,-1+r]}$ si $F(x)_{(0,0)} = 0$ satisfont les conditions données dans la proposition 3. D'où,

$$ egin{cases} F^2(x)_{(0,-1)} \in \{1,2\} \text{ et } \forall (i,j) \in \{\mathbb{Z} \times \}-\infty, -2\} \cup \{[1, +\infty \times \{-1\}], F^2(x)_{(i,j)} = x_{(i,j)} & \text{si } F(x)_{(0,0)} = 0. \\ F^2(x)_{(1,0)} \in \{1,0\} \text{ et } \forall (i,j) \in \{\mathbb{Z} \times \}-\infty, -1\} \cup \{[2, +\infty \times \{0\}], F^2(x)_{(i,j)} = x_{(i,j)} & \text{si } F(x)_{(0,0)} = 2. \end{cases} $$

En déduit qu'au moins l'une des deux cellules $F^2(x)_{(0,-1)}$ ou $F^2(x)_{(1,0)}$ est erronée. Par induction, on déduit qu'à chaque itération $n \in \mathbb{N}$, il existe un motif P qui satisfait les conditions données dans la proposition 3 et que la configuration $F^n(x)$ contient au moins une cellule erronée. ■
<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /><figcaption>FIGURE 2.11 – Les deux images possibles de $F(x)_{(0,0)}$. La cellule centrale est cadrée en rouge. Les cellules en erreurs sont pointillées. Le rayon $r = 2$.</figcaption></figure>

**Remarque 2** La proposition 3 reste vraie si f ne vérifie pas la condition (b). Le cas général est donné dans la proposition 4 ci-dessous.

**Proposition 4** Soit F un automate cellulaire associé à une règle locale $f : \mathcal{A}^{(2r+1)\times(2r+1)} \to \mathcal{A}$ ayant un voisinage de Moore de rayon $r > 0$. Si l'application de $f$ sur tout motif $P \in \mathcal{S}_s$ lui associe un état qui est différent de $P_{(1,-1)}$ alors l'automate cellulaire F ne résout pas le problème des 3-coloriages.

**Preuve.** Soit F un automate cellulaire ayant un voisinage de Moore de rayon $r > 0$. Soit $f$ sa règle locale associée. Considérons la configuration $x$ définie comme suit (voir la figure 2.10b) :

$$ \begin{cases} x_{(i,j)} = x_{\mathcal{D}}^{+}(i,j) & \text{si } (i,j) \neq (0,1) \\ x_{(0,1)} = x_{\mathcal{D}}^{+}(0,0) = 1. & \end{cases} $$

Supposons que l'image de tout motif $P \in \mathcal{A}^{(2r+1)\times(2r+1)}$ qui satisfait les conditions données en proposition 4 par la règle locale $f$ est différente de $P_{(1,-1)}$. D'où, $F(x)_{(0,0)} \in \{0,2\}$ et

$$ \forall j \in [-\infty, -r-1] \cup [r+2, +\infty[, \forall i \in [-\infty, -r-2] \cup [r+1, +\infty[, F(x)_{(i,j)} = x_{(i,j)}. $$

Considérons l'ensemble $\mathcal{T}$ suivant :

$$ \mathcal{T} = \{ (i, j) \in [-r-1, r] \times [-r, r+1] : F(x)_{(i,j)} \neq x_{(i,j)} \}. $$

On a $\mathcal{T} \neq \emptyset$ car $F(x)_{(0,0)} \in \{0,2\}$. Soit $(i_0, j_0) \in \mathcal{T}$ tel que :

$$ \forall (i, j) \in \mathcal{T}, j_0 \le j \text{ et } i_0 = \max\{i \in \mathbb{Z} : F(x)_{(i, j_0)} \neq x_{(i, j_0)}\}. $$

Comme $F(x)_{(i_0, j_0)} \neq x_{(i_0, j_0)}$, $F(x)_{(i_0, j_0-1)} = x_{(i_0, j_0-1)}$ et $F(x)_{(i_0+1, j_0)} = x_{(i_0+1, j_0)}$ alors $F(x)_{(i_0+1, j_0)} \neq F(x)_{(i_0, j_0-1)}$. D'après la proposition 1, $F(x)_{(i_0, j_0)}$ est une cellule erronée et le motif $F(x)_{[i_0-r, i_0+r] \times [j_0-r, j_0+r]}$ satisfait les conditions de la proposition 4. Par induction, on déduit que l'erreur se propage en direction sud-est à chaque itération de F. Ce qui fait que $\forall n \in \mathbb{N}, F^n(x)$ est non saine. ■

**Remarque 3**

1. Les propositions 3 et 4 restent vraies sous des rotations d'angle $\frac{\pi}{2}$. Autrement dit, si l'image de tout motif $P \in \mathcal{A}^{(2r+1)\times(2r+1)}$ qui est centré en $(0,0)$, $P_{(0,0)}$ est erronée et que $P_{[-r,r]\times[1,r]}$ (resp. $P_{[-r,-1]\times[-r,r]}$, $P_{[1,r]\times[-r,r]}$) est un sous-motif de $x_{\mathcal{D}}^{+}$ est différente de $P_{(-1,1)}$ (resp. $P_{(-1,1)}$, $P_{(1,-1)}$) alors l'automate cellulaire associé ne résout pas le problème des 3-coloriages.

2. Les propositions 3 et 4 sont valides si $x_{\mathcal{D}}^{+}$ est remplacé par $x_{\mathcal{D}}^{-}$.

**Proposition 5** Soit F un automate cellulaire. Soit $f$ sa règle locale associée admettant un voisinage de Moore de rayon $r > 0$. Si l'image par $f$ de tout motif $P \in \mathcal{S}_s$ est $P_{(1,-1)}$ alors $F$ ne résout pas le problème des 3-coloriages en un temps fini.

<footnote n="1">1. Les cellules en positions citées sont des cellules qui ne voient aucun error dans leurs voisinage de Moore.</footnote>
**Preuve.** Supposons que l'image de tout motif P ∈ S_s soit P_{(1,-1)} et considérons la configuration x ∈ V qui est un damier sur {0, 1}. Soit y une perturbation de x définie comme suit :

$$
\begin{cases}
y_{(i,j)} = x_{D(i,j)}^{+} & \text{si } \|i\|_{\infty} \le 2r \text{ et } \|j\|_{\infty} \le 2r \\
y_{(i,j)} = x_{(i,j)} = 1.
\end{cases}
$$

Par hypothèse, on déduit que

$$
\lim_{n \to +\infty} D(F^n(y), x_D^+) = 0
$$

■

2.3.5 Synthèse

Nous avons commencé ce chapitre par l'introduction des notions fondamentales nécessaires
à la compréhension de ces systèmes, avant de nous concentrer plus précisément sur le problème
des 3-coloriages, un problème encore non résolu à ce jour. En particulier, on ne sait toujours pas
si un automate cellulaire peut, en temps fini, stabiliser toute configuration vers un 3-coloriage
valide.

Dans notre analyse, nous avons identifié certaines configurations que nous avons qualifiées
d'uniquement corrigibles, et nous avons étudié leurs évolutions possibles. Il est apparu que ces
configurations évoluent soit en formant des boucles, soit en suivant des chemins ayant à la fois
une entrée et une sortie infinies. Un point intéressant est que nous n'avons observé aucune confi-
guration saine ayant une entrée infinie qui mènerait à une boucle. Cela suggère qu'il existe des
configurations avec un nombre fini d'erreurs, mais qui ne peuvent pas être vues comme de simples
perturbations locales d'une configuration saine.

Pour conclure, nous avons formulé quelques propriétés que devrait vérifier tout automate cel-
lulaire capable de corriger les 3-coloriage. Néanmoins, le problème reste ouvert, et nous ne savons
toujours pas s'il peut être effectivement résolu par un automate cellulaire.
# Chapitre 3

# Auto-correction partielle des 3-coloriages

On n'est correct qu'en corrigeant.

De Joseph Joubert. *Carnets*

Dans ce chapitre, on introduit un automate cellulaire probabiliste F défini sur $\{0, 1, 2\}^{\mathbb{Z}^2}$ qui permet la correction partielle de n'importe quelle configuration perturbée pour les 3-coloriages. La règle locale $f$ associée est directionnelle, elle privilégie des corrections selon la direction est, puis nord. Dans certains cas minoritaires, les corrections se poursuivent à l'infini. Dans l'objectif de caractériser ces derniers, nous allons présenter les motifs de $A^{\mathbb{Z}^2}$ de taille 3 × 3 qui permettent la correction des erreurs sans la création de nouvelles perturbations et d'autres permettant la réorientation des erreurs. Une analyse détaillée de la règle locale est ensuite présentée.

## 3.1 Présentation de la règle locale

Dans cette section, on présente un automate cellulaire qui permet la résolution partielle du porblème des 3-coloriages.

**Définition 3** Une cellule est dite OSE-correcte si sa valeur est différente de la valeur de ses cellules ouest, sud et est. Elle est dite OS-correcte si sa valeur est différente de la valeur de ses cellules ouest, et sud.

<figure><img src="image_31.png" /><figcaption>FIGURE 3.1 – Différents types de correction d'une cellule.</figcaption></figure>

Soit une configuration $\sigma \in A^{\mathbb{Z}^2}$, où $\sigma(i, j)$ est l'état de la cellule de $\sigma$ se trouvant à la position $(i, j) \in \mathbb{Z}^2$. On adoptera les abréviations suivantes : *correcte*(i, j) pour désigner que la cellule en position $(i, j)$ est saine. De la même façon, on définit *OSE-correcte*(i, j) et *OS-correcte*(i, j) pour désigner que la cellule en position $(i, j)$ est *OSE-correcte* ou *OS-correcte*. Soient $G = \{0, 1, 2\} \setminus \{\sigma(i - 1, j), \sigma(i + 1, j), \sigma(i, j - 1)\}$ l'ensemble des corrections locales possibles pour la cellule $(i, j)$ et $q$ le nouvel état de la cellule $(i, j)$ après l'application de la règle locale.
L'application de l'automate cellulaire se fait en appliquant la règle locale suivante selon l'ordre suivant :

1. Si correcte(i, j) alors $q = \sigma(i, j)$.

2. Si OS-correcte(i, j) alors $q = \sigma(i, j)$.

3. Si $\sigma(i, j) = \sigma(i - 1, j)$ et OS-correcte(i - 1, j) et OSE-correcte(i, j - 1) alors :

• Si $card(G) = 0$ alors $q = \sigma(i + 1, j)$;

• Sinon, $q$ prend une valeur aléatoire uniforme dans $G$.

4. Si $\sigma(i, j) = \sigma(i, j - 1)$ et OS-correcte(i, j - 1) et correcte(i - 1, j) alors :

• Si $card(G) = 0$ alors $q = \sigma(i + 1, j)$;

• Sinon, $q$ prend une valeur aléatoire uniforme dans $G^1$.

5. Sinon, $q = \sigma(i, j)$.

**Le voisinage utilisé** : Le voisinage nécessaire pour l'évolution de l'automate cellulaire est représenté dans la figure 3.2 où la cellule centrale est coloriée en rouge.

<figure><img src="image_32.png" /><figcaption>FIGURE 3.2 – Le voisinage de l'automate cellulaire.</figcaption></figure>

### 3.1.1 Pour quel comportement ?

Dans cette partie, on revient sur les différentes conditions qui définissent la règle locale dont l'objectif est de donner une illustration détaillée du comportement résultant de chaque conditionnement.

**Première condition** : nécessaire par définition du problème.

**Deuxième condition** : Cette condition fait réduire les corrections aux corrections du nord et de l'est. Elle précise la direction de correction consistant à considérer toute cellule dont la valeur est différente de la valeur de sa cellule sud et ouest est fixe. Ce qui signifie que toute cellule erronée dont l'erreur parvient en son nord ou est n'est pas concernée par le processus de correction.

**Troisième condition** : Cette étape a pour objectif la correction des erreurs se trouvant au niveau des lignes de la configuration perturbée à condition que les cellules constituant la ligne de dessous de la cellule à corriger soient au moins OSE-correctes. Cette condition s'applique sur les cellules dont la valeur est égale à la valeur de la cellule se trouvant à leur ouest. Plus encore, la cellule sud de la cellule à corriger est OSE-correcte tandis que sa cellule ouest est OS-correcte. Ces conditions sont conçues dans le sens à ce que les corrections commenceront à partir des premières erreurs lignes se trouvant au-dessus des lignes correctes que la configuration perturbée contient. La figure 3.3 fait une illustration du cas général d'application de cette condition. Dans la figure 3.4, on présente quelques exemples d'applications.

**Remarque 4** Notons que la troisième condition s'applique aussi sur les cellules qui vérifient cette dernière et qui de plus leur valeur est égale à la valeur de leur cellule sud comme on peut le voir sur la figure 3.5. Cela permet de mieux illustrer l'ordre des corrections et les cellules à corriger. En effet, le motif de la figure 3.5 a trois cellules en erreur mais il y a uniquement une cellule qui est impliquée dans le processus de correction et qui est non OS-correcte. La valeur des deux autres cellules sont fixes sous les applications de l'automate cellulaire.

<footnote n="1">1. Notons que dans ce cas, G admet une seule valeur.</footnote>
<figure><img src="image_33.png" /><figcaption>FIGURE 3.3 – Cas d'application de la troisième condition.</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>FIGURE 3.4 – Exemples d'applications de la condition 3.</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>FIGURE 3.5 – Cas d'égalité entre les cellules sud, ouest avec une cellule satisfaisant la troisième condition.</figcaption></figure>

**De l'aléa dans la troisième condition :** Par définition même de la règle locale, on observe bien que lors de l'application de la troisième condition, la valeur que la cellule prendra est choisie d'une façon aléatoire et uniforme parmi deux valeurs possibles. Ce cas est valable quand la valeur de la cellule concernée par la correction est égale à la valeur de ses cellules ouest, est et sud (voir la figure 3.6a). Peu importe la valeur choisie pour la cellule, cette dernière deviendra, après l'application de F, une cellule OS-correcte. L'importance de l'aléa réside dans la probabilité positive qu'une cellule ait sa juste valeur. En effet, étant donné que la correction des 3-coloriages est sensible aux choix de correction, c'est-à-dire que dans certains cas, effectuer une cellule par une valeur $a \in A$ au lieu d'une autre valeur $b \neq a$, malgré que les deux valeurs assurent une correction locale de la cellule concernée, on constate que l'une des valeurs pourra générer des perturbations lointaines par rapport à la cellule choisie tandis que l'autre pas. La figure 3.6b représente un exemple d'un tel motif où le choix de la valeur d'une seule cellule a un effet décisif sur l'apparition de nouvelles perturbations au niveau des cellules à une distance assez longue qu'on le veut par rapport à la première cellule affectée. Cet aléa garantit donc que de tels cas sont irréalisables avec une probabilité strictement positive.
<figure><img src="image_36.png" /><figcaption>FIGURE 3.6 – L’aléa de la règle locale.</figcaption></figure>

**Quatrième condition** : Cette condition est la version verticale de la troisième condition. Telle que la cellule à corriger devra être égale à sa cellule sud. De plus, sa cellule sud devra au moins être OS-correcte, tandis que sa cellule ouest devra être saine. Ces deux dernières conditions reflètent simplement le fait qu'aucune correction ne sera lancée si la cellule erronée elle-même ne se trouve pas au-dessus des cellules et à coté des cellules qui sont au moins OS-correctes.

La figure 3.7 illustre le cas général d'application de cette condition et en figure 3.8 on donne quelques exemples d'applications de cette condition.

<figure><img src="image_37.png" /><figcaption>FIGURE 3.7 – Cas d'application de la quatrième condition.</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>FIGURE 3.8 – Exemples d'applications de la quatrième condition.</figcaption></figure>

**Remarque 5**

1. La quatrième condition définissant la règle permet de garder l'ordre de correction imposé qui est de la gauche à la droite, ensuite, du bas en haut. On donne un motif exemple dans la figure 3.9a où on observe bien par l'application de F que la cellule a n'est corrigée qu'une fois les deux cellules b et c sont au moins OS-correctes.
2. On peut penser que la quatrième condition est un atout vu que la troisième condition définissant la règle locale assure les corrections lignes et comme les perturbations effectuées sont finies alors les corrections pourront se faire ligne par ligne sans avoir à prendre les corrections colonnes en considération. Ce qui n'est pas le cas car c'est grâce à l'application de cette quatrième condition que le motif représenté dans la figure 3.9b pourra se corriger.

3. L'ensemble $G = \{0, 1, 2\} \setminus \{\sigma(i, j-1), \sigma(i, j+1), \sigma(i-1, j)\}$ où la quatrième condition s'applique sur la cellule en position $(i, j)$ admet une seule valeur. En effet, comme la cellule en position $(i, j-1)$ est saine et que $\sigma(i, j) = \sigma(i-1, j)$ alors on a forcément $\sigma(i-1, j) \neq \sigma(i, j-1)$.

<figure><img src="image_39.png" /><figcaption>FIGURE 3.9 – Illustration pour la remarque 5.</figcaption></figure>

## 3.2 Exemples numériques

On présente dans cette partie des exemples de simulations obtenus par l'application de l'automate cellulaire.

Le code de couleur est le suivant : cellule blanche correspond à l'état 0, cellule noire à 1, cellule rouge à 2. Les cellules jaunes sont des cellules en erreur.

**Example 3** Illustration d'une correction localement non bornée pour un motif ayant un nombre fini d'erreur.

<figure><img src="image_40.png" /><figcaption>FIGURE 3.10 – Exemple de simulation d'une correction localement non bornée.</figcaption></figure>
<figure><img src="image_41.png" /><figcaption>FIGURE 3.11 – Exemple de simulation d'une correction finie.</figcaption></figure>

**3.3 La stratégie de correction**

La figure 3.12 représente un exemple d'un motif ayant seulement deux cellules en erreur mais leur correction nécessite le changement de plus de deux cellules. Dans de tels cas, on déduit que les corrections doivent prendre en considération des cellules se trouvant assez loin qu'on le veut de l'origine des perturbations.

<figure><img src="image_42.png" /><figcaption>FIGURE 3.12 – Exemple d'une configuration où une correction locale n'est pas possible.</figcaption></figure>

Ceci implique que toute solution *raisonnable* devra créer de nouvelles perturbations afin de corriger localement cette configuration. Dans cas, nous allons proposé un processus de correction qui permet dans certains cas de générer de nouvelles perturbations se propageant loin de leur origine. Cette propagation se fait suivant la direction est, puis nord. Ce qui rend les propagations bornées pour la majorité des conditions initiales prises au départ.

**Notation 6** Soit P un motif de $A^{Z^2}$ de taille $3 \times 3$.

* On dit que le motif P consomme les erreurs s'il permet la correction des erreurs sans la génération de nouvelles erreurs.

* Toute cellule ayant la même valeur que sa cellule est ou ouest (resp. nord ou sud) est appelée erreur ligne (resp. erreur colonne). Sa longueur est égale au nombre de cellules qui sont égales horizontalement (resp. verticalement).

* On dit que le motif P redirige une erreur s'il change la direction de l'erreur, d'une erreur ligne (propagation horizontale) à une erreur colonne (propagation verticale) et vice versa.

* On dit qu'une erreur ligne (resp. erreur colonne) de longueur 2 se propage vers la direction est, (resp. vers la direction nord) si la correction des cellules erronées engendre une nouvelle erreur ligne (resp. erreur colonne) de longueur au moins 2 à droite (resp. au-dessus) des cellules corrigées.
**Définition 4** Soit P un motif dans $\mathcal{A}^{3 \times 3}$. Les cellules de P sont désignées suivant leurs positions dans le voisinage de Moore de rayon 1. (C, N, S, E, O, NE, NO, SE et SO).

1. Le motif P consomme les erreurs lignes se propageant en direction est si $C = NW = SW$.

2. Le motif P consomme les erreurs colonnes se propageant en direction nord si $C = SE = SW$.

3. Le motif P redirige une erreur ligne en erreur colonne ou une erreur colonne en une erreur ligne si $C = SW$. La redirection de l'erreur ligne ou colonne dépend de la position de l'erreur par rapport à ce motif. (voir les figures 3.13 et 3.14).

La figure 3.13a illustre un motif de taille 3 × 3 tel que $C = SW = O$ et sa cellule W est erronée. Dans ce cas, la cellule ayant l'état a est corrigée en premier en un état a'. Ensuite, deux cas sont possibles : a) Il existe un état $c'$ qui corrige l'erreur (figure 3.13b), ou bien b) La valeur de $c'$ est différente de ses cellules est, sud et ouest (figure 3.13c), dans ce cas, l'erreur ligne est redirigée en une erreur colonne.

<figure><img src="image_43.png" /><figcaption>FIGURE 3.13 – Redirection d'une erreur ligne en une erreur colonne. Les lignes pointillées représentent la position du motif 3 × 3 qui redirige l'erreur. Les cellules vertes et rouges sont les cellules saines et erronées respectivement. Les O-cellules jaunes sont les cellules C et SW du motif.</figcaption></figure>

Dans le cas où la cellule a est corrigée en une cellule OSE-correcte alors suivant le résultat de correction de la cellule c, au moins une erreur colonne en résultera. L'apparition de deux erreurs colonnes, une au niveau de la cellule a et l'autre au niveau de la cellule c, pourra également former des erreurs lignes au niveau de la ligne au-dessus des cellules a et c.
Selon les mêmes arguments, la figure 3.14 représente les cas où une erreur colonne est redirigée en une erreur ligne.

<figure><img src="image_44.png" /><figcaption>FIGURE 3.14 – Redirection d'une erreur colonne en une erreur ligne. Les lignes pointillées représentent la position du motif 3 × 3 qui redirige l'erreur. Les cellules vertes et rouges sont les cellules saines et erronées respectivement. Les O-cellules jaunes sont les cellules C et SW du motif.</figcaption></figure>

### 3.3.1 Les motifs consommateurs d'erreurs :

On présente dans la figure 3.15 un exemple où une erreur ligne est consommée. Telle que la correction de la cellule a assure l'existence d'un état rendant la cellule b valide. En considérant une rotation d'angle $\frac{\pi}{2}$ dans le sens trigonométrique pour la figure 3.15, on visualise le cas des motifs consommateurs des erreurs colonnes.
<figure><img src="image_45.png" /><figcaption>FIGURE 3.15 – Consommation d'une erreur ligne.</figcaption></figure>

⚠️ **IMPORTANT!** Les motifs consommateurs ou redirecteurs d'erreurs lignes ou colonnes ne se limitent pas qu'à la correction de ces deux cellules erronées mais ils permettent aussi la correction de toutes les cellules en erreur se propageant en leur direction et qui sont sur la ligne ou la colonne de correction de ce dernier.

⚠️ **IMPORTANT!** Soit un motif P tel que $C = SW = NE = W=0$ et $N = E = 1$. On suppose que le centre C se trouve à une certaine position $(i, j)$. Soit une erreur donnée se propageant de la gauche à droite et en direction ouest de ce motif P, (voir la figure 3.16). Alors, l'erreur sera consommée par P si le motif P n'était pas modifié avant la correction de la cellule en position $(i-1, j)$. La figure 3.16 présente un cas bien qu'un motif qui redirige une erreur ligne en une colonne soit présent à droite d'une erreur donnée, ce dernier n'a aucune influence sur la correction de l'erreur elle-même, vu qu'il est déjà en erreur. De plus, le fait qu'il soit en erreur n'est pas l'unique raison de son inutilité, car il pourra bien être modifié et corrigé lui-même avant de pouvoir s'en servir pour consommer ou rediriger l'erreur venant dans sa direction de consommation ou redirection. Ce qui fait qu'une erreur se propageant de gauche à droite soit consommée par un motif particulier est lié à l'existence du motif lui-même au moment de la correction de l'erreur.

<figure><img src="image_46.png" /><figcaption>FIGURE 3.16 – Motif redirecteur d’erreur en erreur.</figcaption></figure>

Notons que si un tel motif n'est pas perturbé en aucun cas, alors toute erreur venant en sa direction de consommation pourra être soit corrigée, soit réorientée vers la ligne qui est au-dessus, peu importe si ce motif avait déjà corrigé d'autres erreurs passées précédemment en sa direction de consommation ou pas.

## 3.4 Analyse de la règle

Deux configurations $x, y \in \mathcal{A}^{\mathbb{Z}^2}$ tel que $x \neq y$, sont dites proches l'une de l'autre si les valeurs de ces deux dernières sont égales sur un carré centré de longueur $2k+1$ avec $k \in \mathbb{N}$ assez large.

**Définition 5** Soient $x \in V$ une configuration légale de $\mathcal{A}^{\mathbb{Z}^2}$ et $y \in \tilde{V}$ une perturbation finie de x. On dit que la configuration y est corrigée à l'infini sous les applications d'un automate cellulaire F si :

$$ \exists x' \in V, \lim_{n \to +\infty} D(F^n(y), x') = 0, $$

où, $F^n(y)$ est le $n^{\text{ième}}$ itéré de y par F.
**Théorème 1** Soit F l'automate cellulaire définit précédemment, alors, toute configuration perturbée $x \in \tilde{V}$ satisfait l'une des propriétés suivantes :

1. Il existe un entier $n \in \mathbb{N}$ (fini) tel que $F^n(x) \in V$.

2. La configuration $x$ est corrigée à l'infinie.

**Preuve.** Soient $x$ une configuration erronée de $\mathcal{A}^{\mathbb{Z}^2}$ contenant un nombre fini d'erreurs et $L$ la longueur du plus petit carré contenant ces erreurs. On suppose que la première ligne, supposée la ligne 0, de ce carré contient déjà au moins une erreur ligne et que sans perte de généralité, on suppose que la cellule (0,0) est la première cellule qui est erronée. i.e., on a soit $x_{(0,1)} = x_{(0,0)}$ soit $x_{(1,0)} = x_{(0,0)}$ comme le montre la figure 3.17a.

L'application de la règle locale sur les cellules $x_{(0,0)}$, $x_{(0,1)}$ et $x_{(1,0)}$ donne les résultats suivants :

* la cellule à l'origine est OS-correcte. D'où, $F(x)_{(0,0)} = x_{(0,0)}$.

* La cellule (1,0) satisfait la troisième condition définissant la règle locale, elle sera donc changée en un élément de $\{0, 1, 2\}$ et deviendra OS-correcte. Notons que la nouvelle valeur qu'aura cette cellule ne sera jamais modifiée par les prochaines itérations de l'automate cellulaire.

* De même, la cellule (0,1) sera modifiée en une cellule qui sera au moins OS-correcte par application de la quatrième condition définissant la règle locale.

En déduit, que la première itération de F corrige la cellule (0,0) et rend les cellules en positions (0,1) et (1,0) au moins OS-correctes et fixes tout au long des prochaines itérations (voir la figure 3.17b).

Par définition même de la règle locale, il est trivial que les corrections lignes se font indépendamment des corrections colonnes et que chaque correction de l'automate cellulaire corrigera soit une cellule ou créera au moins une cellule qui est OS-correcte. On illustre dans la figure 3.17c le résultat d'application de la seconde itération de F.

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

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

<figure><img src="image_49.png" /><figcaption>FIGURE 3.17 – Éléments de preuve du théorème 1. Deux cellules liées par une flèche sont deux cellules dont les valeurs correspondantes sont différentes.</figcaption></figure>

Regardons la ligne 0. On suppose que cette ligne contient au moins un motif de taille 3×3- qui consomme ou redirige les erreurs ligne en erreurs colonnes. Le centre de ce motif est en position $(j,0)$ où $j \ge L$, i.e, il est positionné en dehors et à droite du carré contenant l'ensemble des erreurs initiales. De plus, on suppose que ce motif n'est pas perturbé par les corrections effectuées au niveau des lignes $i$ avec $i \in \mathbb{N}: i \le 1^2$. On déduit, qu'il existe un entier $n_0 \in \mathbb{N}$ tel que toutes les cellules qui sont sur la ligne 0 de la configuration $F^{n_0}(x)$ sont soit correctes soit OSE-correctes.

En appliquant le même argument sur toutes les lignes en erreur et en raisonnant sur la présence ou la non présence des motifs redirigeant ou consommant des erreurs lignes, on déduit que chaque ligne $i$ est : (1) soit est corrigée, i.e. il existe $n_i \in \mathbb{N}$ tel que toutes les cellules se trouvant sur ligne $i$ de la configuration $F^{n_i}(x)$ sont soit correctes ou OSE-correctes, ou bien (2) il existe une erreur ligne à une certaine position $(k, i)$ pour $k \in \mathbb{N}$ tel que à chaque $i^{ème}$ itération de F, la cellule $(k+n, i)$ est au moins OS-correcte tandis que la cellule $(k+n+1, i)$ est erronée. Autrement dit, $F^n(x)_{(k+n+1,i)} = F^n(x)_{(k+n+2,i)}$.

<footnote n="2">2. Dans le cas général, $i \le k+1$ tel que le motif qui redirige ou consommateur des erreurs horizontales se trouve sur la ligne $k$.</footnote>
On conclut que l'application de F sur la configuration $x$ satisfait l'un des quatres cas suivants :

1. Si toute ligne en erreur de la configuration perturbée $x$ est corrigée à l'itéré $n_i$ alors il existe un entier $n = \max_{i \in \mathbb{Z}} n_i$ tel que la configuration $F^n(x)$ est saine.

2. Supposons qu'il existe un entier $n_j \in \mathbb{N}$ tel qu'il existe des cellules constituant une certaine ligne $i$ de la configuration $F^{n_j}(x)$ qui sont OSE-correctes et non saines (erreurs colonnes au niveau de la ligne $i$) tandis que le reste de toutes les cellules de $F^{n_j}(x)$ sont saines. Sans perte de généralité, on suppose que $F^{n_j}(x)_{(0,i)} = F^{n_j}(x)_{(0,i+t+1)}$ et qu'il existe un entier $t' \in \mathbb{N}$ tel que le résultat de correction de la cellule $(0, i+t+1)$, $\forall t \in \mathbb{N}: t \le t'$ à l'itéré $n_j + t$ donne $F^{n_j+t+1}(x)_{(0,i+t+1)} = F^{n_j+t+1}(x)_{(0,i+t+2)}$. Dans ce cas, s'il existe un motif consommateur des erreurs verticales centré à la position $(0, i+k)$ avec $k \in \mathbb{Z}: i+k \ge L$ qui n'est pas perturbé par les corrections effectuées au niveau des lignes $i'$ et des colonnes $j'$ tel que $i' \le i+k$ et $j' \le 0^3$ alors il existe un entier $n \in \mathbb{N}$ tel que toutes les cellules constituant la colonne 0 de la configuration $F^n(x)$ sont saines.

En généralisant cet argument sur toutes les colonnes de $x$ et sous les itérations de F, on déduit que si dans le cas où les corrections par l'automate cellulaire font propager les erreurs colonne du bas en haut et il existe des motifs consommateurs des erreurs verticales qui stopperont la propagation de ces dernières alors il existe $n \in \mathbb{N}$ tel que $F^n(x)$ est saine.

3. Aucun des deux cas précédents n'est satisfait, i.e, il existe au moins une ligne $i'$ où les erreurs se propagent en direction est tout en restant sur la ligne $i'$ sans que ces erreurs soient consommées ou il existe au moins une colonne $j'$ qui n'a aucun motif consommateur d'erreurs pour arrêter la propagation des erreurs au niveau de la colonne $j'$. Dans ce cas, les corrections se poursuivront indéfiniment tout en s'éloignant de l'origine. Autrement dit, il existe un entier $n \in \mathbb{N}$ tel que le motif $F^n(x)_{[-k,k] \times [-k,k]}$ satisfait la règle des 3-coloriage et tel que $k \to +\infty$ quand $n \to +\infty$.

4. Toute ligne et toute colonne de $x$ admet des motifs qui réorientent les erreurs lignes en erreurs colonnes et des motifs réorientant les erreurs colonnes en erreurs lignes. Dans ce cas, les erreurs se propagent en direction nord-est indéfiniment et tout en s'éloignant de l'origine des perturbations.

On déduit que, soit la configuration $x$ est corrigée en un temps fini soit il existe une configuration $x' \in V$, tel que les configurations $F^n(x)$ et $x'$ sont proches l'une de l'autre, quand $n$ tend vers l'infini. ■

**Remarque 6** Étant donné que les corrections au niveau des lignes exigent à ce que les cellules constituant la ligne d'en dessous soient OSE-correctes. Cela fait que les correction ligne sont des corrections non simultanées (voir la figure 3.18). De la même façon, on déduit que les corrections au niveau des colonnes ne sont aussi pas simultanées.

<figure><img src="image_50.png" /><figcaption>FIGURE 3.18 – Correction non simultanée entre deux lignes successives.</figcaption></figure>

<footnote n="3">3. Dans le cas général, $j' \le i$ où le motif consommateur des erreurs verticale se trouve sur la colonne $i$.</footnote>
3.5 Étude des erreurs se propageant à l'infini

Suite à des simulations numériques, on constate très souvent que les erreurs se propageant à l'infini ont la géométrie du motif donné dans la figure 3.19. En observant ce dernier, on réalise que le phénomène apparaît quand on a des cellules qui forment deux diagonales de la même couleur (les cellules rouges des motifs de la figure 3.19) séparées exactement par deux autres diagonales de couleurs différentes qui se dirigent selon la direction nord-est. On appelle ce type d'erreur par *les erreurs nord-est*. Le motif de la figure 3.19b est l'image par F du motif donné dans la figure 3.19a. On conclut que le processus de correction de F ne peut pas prévoir l'apparition de tels motifs qui ne sont rien d'autre que des sous-motifs d'une configuration uniquement corrigible présentée à la section 2.3.1.

<figure><img src="image_51.png" /><figcaption>FIGURE 3.19 – Motif incorrigible par F. Deux cellules coloriées avec la même couleur sont deux cellules associées au même état dans A.</figcaption></figure>

Soit $y$ une perturbation sur $\mathcal{A}^{Z^2}$. Étant donné que l'automate cellulaire $F$ est probabiliste et en se basant sur l'argument donné sur la sensibilité des 3-coloriages face aux choix d'une cellule valide (figure 3.6b) quand cela est possible, alors pour la même perturbation $y$, on déduit qu'avec une probabilité strictement positive une erreur nord-est peut être créée ou ne pas être créée lors des itérations de $F$. De plus, dépendant des motifs sains que $y$ contient en ses position nord-est avant l'application de $F$, les erreurs nord-est peuvent émerger au long des itérations de $F$ avec les motifs sains que $y$ possède et donc l'erreur nord-est est localement consommée. Ce qui fait qu'avec une probabilité strictement positive, les erreurs nord-est peuvent être consommées au long des itérés de $F$. La figure 4.3.1 illustre un exemple d'un tel cas.

<figure><img src="image_52.png" /><figcaption>FIGURE 3.20 – Correction d'une erreur nord-est. La flèche représente l'intersection de la région en perturbation (en dessous) avec la région saine (au dessus).</figcaption></figure>
**Remarque 7** Étant donné que l'automate cellulaire F corrige uniquement les cellules en erreur, alors le cas de la figure 3.6b peut se produire si les perturbations initiales d'une configuration donnée $x \in V$ ont échangé des motifs sains en d'autre motifs sains en direction sud ou ouest de l'origine des perturbations. Par conséquent, une cellule a été fixée<fnref n="4" /> à un état valide donné peut générer des perturbations non bornées lointaines.

Dans l'objectif d'avoir une caractérisation globale des corrections se propageant à l'infini, la proposition 6 et la remarque 8 précisent les régions saines qui permettent l'existence de tels cas. Ceci donne une représentation générale des cas rarissimes des propagations infinies d'erreurs en direction est ou nord.

**Proposition 6** Soit $x \in \tilde{V}$. On suppose que la ligne 1 de $x$ admet une erreur ligne en position $(-2, 1)$ et que toutes les cellules constituant les lignes $i \in \mathbb{Z}$ de $x$ avec $i \le -1$ soient saines et que les cellules constituant la ligne 0 de $x$ sont soit correctes soit OSE-correctes. De plus, on suppose que la cellule $(-2, 1)$ est OS-correcte. Alors, sous les itérations de F, les erreurs de la ligne 1 se propageront à l'infini en direction est tout en restant sur la ligne 1 si et seulement si $x$ est de la forme présentée dans la figure 3.21. Formellement, les erreurs de la ligne 1 de $x$ se propageront à l'infini en direction est s'il existe un entier $j \in \mathbb{Z}$ tel que $\forall k \in \mathbb{N}$ on a :

$$x_{(j+2+3k,1)} = x_{(j+3k,0)} = x_{(j+3k+3,0)}, \quad x_{(j+3k,1)} = x_{(j+1+3k,0)} = x_{(j+3k+3,1)} \quad (3.1)$$

$$\text{et } x_{(j+2+3k,0)} = x_{(j+1+3k,1)} = x_{(j+4+3k,1)}. \quad (3.2)$$

De plus,

$$x_{(j-1,1)} = x_{(j,0)} = x_{(j-2,1)} \text{ et } x_{(j-1,0)} = x_{(j+1,1)} \text{ et OS-correcte}(j-2,1). \quad (3.3)$$

<figure><img src="image_53.png" /><figcaption>FIGURE 3.21 – Erreur est. L'origine du repaire est en position $(j, 0)$. La ligne 0 et 1 du motif chacune est la concaténation infinie d'un sous-motif dans $\mathcal{A}^{1 \times 3}$.</figcaption></figure>

**Preuve.** Soit $x \in \tilde{V}$ tel que toutes les cellules constituant les lignes $i \in \mathbb{Z}$ de $x$ avec $i \le -1$ soient saines et que les cellules constituant la ligne 0 de $x$ sont soit correctes soit OSE-correctes. Sans perte de généralité, on suppose que la cellule en position $(-2, 1)$ est OS-correcte<fnref n="5" /> et que $x_{(-1,1)} = x_{(-2,1)}$. La correction de la cellule $(-1, 1)$ se propage à l'infini dans la direction est si et seulement si tout motif de taille $3 \times 3$ centré sur une position $(j, 1)$ avec $j \in \mathbb{N}$ est un motif qui ne redirige pas les erreurs ligne en erreur colonne et qui ne les consomme pas. Ce qui fait que l'unique motif qui vérifie $x_{(j,1)} \neq x_{(j-1,0)}$, $\forall j \in \mathbb{N}^6$ satisfait les équations 3.1, 3.2 et 3.3. Une application directe de la règle locale montre qu'à chaque pas de temps $n \in \mathbb{N}$, la cellule en position $(n-1, 1)$ est OS-correcte mais non pas OSE-correcte tandis que la cellule en position $(n, 1)$ satisfait $x_{(n-1,1)} = x_{(n,1)}$, qui est donc en erreur.

■

<footnote n="4">4. Toute cellule OS-correcte reste fixe sous les applications de F si aucune erreur ne s'est propagée en sa direction.</footnote>

<footnote n="5">5. Cette condition assure le fait que la cellule en position $(-1, 1)$ est considérée par F pour une correction.</footnote>

<footnote n="6">6. Cette condition est équivalent à l'absence des motifs consommateurs ou redirigeurs des erreurs se propageant de gauche à droite.</footnote>
**Remarque 8** Avec une rotation d'angle $\frac{\pi}{2}$ dans le sens trigonométrique du motif infini donné dans la figure 3.21. Avec les mêmes arguments qu'avec la proposition 6, on déduit que les erreurs colonnes se propagent en direction nord tout en restant sur la même colonne sous les itérés de F si et seulement si la configuration perturbée x est de la forme présentée dans la figure 3.22a.

**Remarque 9** Soit y une perturbation d'une configuration saine x. Supposons que les perturbations de y soient incluses dans un carré $[-n, n] \times [-n, n]$ pour $n \in \mathbb{N}$. En se basant sur les motifs initiaux sains que y contient aux positions $[n, +\infty[ \times [-n, \infty[$, on peut prévoir si les corrections de y sont infinies en direction est. (Idem pour la direction nord). Les figures 3.22b et 3.22c représentent les deux géométries possibles des régions saines qui permettent la propagation des erreurs est ou nord. Rappelons que ces régions ne sont rien d'autre que les concaténations infinies de sous-motifs issus des configurations uniquement corrigibles.

<figure><img src="image_54.png" /><figcaption>FIGURE 3.22 – Erreur nord ou est. Les lignes rouges des motifs 3.22b et 3.22c lient les diagonales ayant le même état entre elles. La propagation de l'erreur en direction est ou nord dépend de la position de l'erreur par rapport à ces régions qui sont la concaténation infinie en direction est ou nord des motifs présentés.</figcaption></figure>

**Remarque 10** Soit x une configuration dont ses motifs en position $[0, +\infty[ \times [-\infty, 0]$ coïncident avec le motif présenté dans la figure 3.22b. Les cellules en position $[0, +\infty[ \times \{1\}$ peuvent être complétées uniquement de deux façon possibles qui sont (1) soit les cellules complètent la diagonale de la ligne 0 en gardant sa direction ou bien (2) les cellules complètent la diagonale de la ligne 0 en changeant sa direction. Ce type de motif, peut stopper la propagation des erreurs est si aucune erreur ligne ne satisfait la proposition 6. Le même argument s'applique sur les erreurs nord.

## 3.6 Synthèse

Dans ce chapitre, on a construit un automate cellulaire corrigeant partiellement le problème des 3-coloriages. Ce dernier adapte un processus de correction se basant sur (1) des corrections directionnelles qui vont en direction nord et est (2) sur la caractérisation des motifs de taille $3 \times 3$ contenant dans des régions saines et qui assurent la non-propagation ou la redirection de ces erreurs. L'automate cellulaire ainsi construit permet la correction de la majorité des perturbations en un temps fini. Dans le cas contraire, trois type d'erreur sont observés : les erreurs nord-est, les erreurs nord ou les erreurs est. On a démontré que (1) les erreurs nord et les erreurs est sont des erreurs résultant de la perturbation de la configuration ayant leurs parties nord, est ou nord-est identiques à celle d'une configuration uniquement corrigible. (2) Les erreurs nord-est sont des erreurs qui peuvent ne pas être créée ou qui peuvent être consommées sous les itérations de F avec une probabilité strictement positive.
Notre travail répond à une version faible du problème des 3-coloriages. L'automate cellulaire $F$ est construit dans le sens à répondre au mieux aux questions suivantes :

* Supposons qu'il n'existe aucune règle locale définie sur $\mathcal{A}^{\mathbb{Z}^2}$ qui résout complètement le problème des 3-coloriages en un temps fini. Dans ce cas, les questions naturelles suivantes se posent :

1. Quel est le plus grand sous-ensemble de configurations perturbées dans $\mathcal{A}^{\mathbb{Z}^2}$ qui peuvent être corrigées par automate cellulaire?

2. Peut-on construire un automate cellulaire minimisant le nombre de cellules en erreur d'une perturbations données $y$ au fil des itérations. Autrement dit, soit $p-0$ le nombre d'erreurs que la perturbations $y$ contient à la condition initiale, existe-il un AC $F$ tel que $p_{n+1} \le p_n$, où $p_n$ est le nombre de cellule en erreur que la configuration $F^n(y)$ contient.

* Admettant que la probabilité d'avoir un AC corrigeant le problème des 3-coloriages est as-sez élevée. Le cas des configurations se corrigeant en temps infinie par $F$, nous donne des informations précises sur les propriétés qu'un automate cellulaire répondant au problème devra satisfaire.
# Perspectives

Pour de futurs travaux et directions dans le cadre d'auto-correction des 3-coloriages, on présente les perspectives suivantes :

**Question 4** Est-il possible de construire une règle locale pour un automate cellulaire déterministe ou probabiliste pour les 3-coloriages où toute configuration est corrigée en un temps fini sur un alphabet de taille 3 ?

**Question 5** Est-il possible de prouver que le problème des 3-coloriages est non soluble i.e., peut-on démontrer que tout automate cellulaire, peu importe son mode de correction pour les 3-coloriages, il existerait une configuration dans $\mathcal{A}^{\mathbb{Z}^2}$ qui le mettrait à défaut ?

Il n'est pas difficile de voir que la complexité des 3-coloriages réside dans les perturbations effectuées avant même de considérer aucun processus de correction. Alors,

**Question 6** Les perturbations des 3-coloriages sont-elles toutes pareilles ? Autrement dit, Peut-on soustraire des caractéristiques particulières qui permettront de partager les perturbations en au moins deux catégories différentes tel que le problème est soluble pour une certaine catégorie et non soluble pour d'autres ?

Une direction importante à prévoir consiste à considérer l'automate cellulaire définit au chapitre 3 résolvant partiellement les 3-coloriages et de traiter sous des conditions supplémentaires et locales toute erreur se propageant à l'infini une fois que cette dernière est apparue. On commence donc par les questions suivantes :

**Question 7** A-t-on d'autres motifs erronés autres que celui présenté en figure 3.19 sur lesquels les corrections par F se propageront à l'infini ?

**Question 8** Quelles modifications peut-on apporter sur F pour que les erreurs se corrigeant à l'infini soient localement corrigibles ? Cela est-il faisable dans des régions spécifiques ? Si oui, lesquelles ?

Une autre approche pour résoudre ce problème est d'autoriser à ce que la taille de l'alphabet soit plus grande que 3. Autrement dit, on considère sur l'alphabet $\mathcal{A}$ de nouveaux symboles, on dénote par $\mathcal{A}'$ le nouvel alphabet, sur lequel on construit un automate cellulaire qu'en partant d'une configuration perturbée de $\mathcal{A}^{\mathbb{Z}^2}$, l'automate cellulaire pourra évoluer dans $\mathcal{A}'^{\mathbb{Z}^2}$ sachant qu'en un temps fini la configuration prise au départ sera corrigée dans $\mathcal{A}^{\mathbb{Z}^2}$. Les symboles à considérer aideront dans le processus de correction mais seule la règle locale associée est responsable de l'apparition et de la disparition de ces symboles.
# Chapitre 4

## Exploration des 4-coloriages par automates cellulaires probabilistes

In ne faut pas y aller par quatre chemins.

Expression française.

Ce chapitre s'intéresse au problème des 4-coloriages sur $\mathbb{Z}^2$, en adoptant une approche différente basée sur un automate cellulaire probabiliste. Nous nous appuyons sur une règle introduite par Fatès, Marcovici et Taati [6], qui applique des transitions locales selon un processus aléatoire, avec pour objectif de corriger progressivement les erreurs de coloriage. Nous avons commencé à analyser cette règle en identifiant certains mécanismes de correction qu'elle met en œuvre, ainsi que des comportements caractéristiques observés lors de l'évolution de configurations perturbées. Cette étude marque une première étape vers une compréhension plus fine du comportement de la règle proposée.

### 4.1 Préliminaires

Dans cette section, on présente brièvement la version probabiliste des coloriages par automates cellulaires.

**Définition 6 (Automate cellulaire probabiliste)** Un automate cellulaire probabiliste est un automate dont la règle locale est une fonction $f: \mathcal{A}^{|V|} \to \mathcal{M}(\mathcal{A})$ où $\mathcal{M}(\mathcal{A})$ représente l'ensemble des distributions de probabilité sur $\mathcal{A}$. L'automate cellulaire probabiliste $F$ défini par la fonction locale $f$ associe une configuration $x$ avec une mesure de probabilité $\mu$ tel que pour tout ensemble fini $C \in \mathcal{G}$, on a

$$ \mu(\{y : \forall i \in C, y_i = v_i\}) = \prod_{i \in C} f(x_{i+v_1}, \dots, x_{i+v_{|V|}})(\{v_i\}). $$

**Remarque 11** Un automate cellulaire probabiliste peut être naturellement interprété comme un processus stochastique discret $(X_0, \dots, X_t, \dots)$, où chaque variable aléatoire $X_t$ représente l'état global du système à l'instant $t \in \mathbb{N}$. À chaque pas de temps, la configuration du système évolue selon la règle de transition probabiliste locale, c'est-à-dire que l'état futur d'une cellule dépend de façon probabiliste de l'état actuel de son voisinage.

**Example 5** Soient $\mathcal{A} = \{0, 1\}$, $\mathcal{G} = \mathbb{Z}$ et $\mathcal{V} = \{0, 1\}$. Soit $p \in ]0, 1[$ et la fonction locale $f$ définie comme suit :

$$ f(x, y) = (1-p)\delta_{(x+y) \mod 2} + p\delta_{(x+y+1) \mod 2}. $$

Cet automate cellulaire peut être considéré comme une perturbation de l'automate cellulaire déterministe $F(x)_i = (x_i + x_{i+1}) \mod 2$.
**Définition 7** Soit F un AC probabiliste défini sur $\mathcal{A}^\mathcal{G}$ associé à une certaine mesure $\mu$. On dit qu'une propriété donnée $\mathcal{P}$ est vérifiée ou satisfaite presque sûrement si l'ensemble des configurations qui ne satisfont pas $\mathcal{P}$ est négligeable. i.e., $\mu(\{x \in \mathcal{A}^\mathcal{G} : x \text{ ne satisfait pas } \mathcal{P}\}) = 0$.

### 4.1.1 Évolution des automates cellulaires

* **L'évolution synchrone** désigne une mise à jour simultanée de l'état de toutes les cellules selon une règle locale commune. À chaque pas de temps, l'ensemble du réseau évolue de manière coordonnée.

* **L'évolution asynchrone** représente le cas où les cellules sont mises à jour individuellement ou par petits groupes, selon un ordre potentiellement aléatoire ou déterminé par une règle spécifique. On distingue deux cas d'asynchronisme dans la mise à jour des cellules :

1. $\alpha$-asynchrone : chaque cellule est mise à jour avec une certaine probabilité $\alpha \in ]0, 1[$ et dans un temps borné, ce qui signifie qu'aucune cellule ne reste inactive indéfiniment.

2. Totalement-asynchrone : à chaque pas de temps, une seule cellule est choisie aléatoirement et uniformément pour être mise à jour.

**Définition 8 (Auto-correction par un AC probabiliste)** *Un automate cellulaire probabiliste est dit auto-correcteur des perturbations finies s'il satisfait les deux conditions suivantes :*

1. Les configurations saines sont fixes. i.e. Si $x^t$ est saine alors $x^{t+1}$ est aussi saine.

2. Toute configuration perturbée converge presque sûrement vers une configuration entièrement saine en un temps fini.

## 4.2 Auto-correction isotropique et probabiliste pour un 4-coloriage

Dans cette section, nous allons travailler sur les 4-coloriages. Soit F l'automate cellulaire défini sur $\{0, 1, 2, 3\}^{\mathbb{Z}^2}$ proposé dans la réf.[6] pour une correction probabiliste des 4-coloriages. L'automate cellulaire F admet un voisinage de von Neuman de rayon 1 où la valeur de chaque cellule de ce voisinage est dénotée suivant sa position nord $q_n$, sud $q_s$, est $q_e$ ou ouest $q_o$. On dénote par $\sigma(i, j)$ la valeur de la cellule en position $(i, j) \in \mathbb{Z}^2$ dans $\mathcal{A}$. Soit $q$ le nouvel état qu'une cellule $(i, j)$ prendra après l'application de F. La règle locale associée à F est définie comme suit :

1. Toute cellule $(i, j)$ saine est fixe, i.e., $q = \sigma(i, j)$

2. Sinon, on considère l'ensemble des corrections locales $G = \{0, 1, 2, 3\} \setminus \{q_n, q_s, q_e, q_o\}$.

(a) Si $card(G) \neq 0$ alors $q$ prendra une valeur aléatoire et uniforme dans $G$;

(b) Sinon, $q$ prendra une valeur aléatoire et uniforme dans $\mathcal{A}$.

### 4.2.1 Quel comportement? Quel rôle de l'aléa?

La présence de l'aléa dans la description même de la règle locale nous dirige envers des directions aléatoires pour la propagation des erreurs. Pour mieux expliquer ce point, nous commençons par détailler le comportement issu de chaque condition constituant la règle locale.

* La première condition est imposée par le problème en question. Cette dernière est bien sensible aux corrections par l'automate cellulaire, autrement dit, une cellule saine peut bien être perturbée au cours de l'évolution de F. Ceci ne permet pas la protection à long terme des régions saines lors de la propagation des erreurs.

* La deuxième condition (2.a) n'est rien d'autre qu'une correction locale des états erronés quand cela est possible. Le fait de choisir une correction aléatoire n'a aucun effet sur la cellule corrigée en elle-même car toute nouvelle valeur que cette dernière prendra sous cette condition fera d'elle une cellule correcte si chaque cellule constituant son voisinage est soit correcte soit fixe. Dans certains cas, comme on peut le voir dans la figure 4.1, cette condition
ne garantit souvent pas une correction pour la cellule concernée contrairement à ce qu'on
pourrait penser.

<figure><img src="image_55.png" /><figcaption>FIGURE 4.1 – Illustration de deux cellules erronées qui peuvent soit être corrigées par la seconde condition, soit rester en erreur.</figcaption></figure>

La figure 4.1 représente un motif ayant deux cellules lignes en erreur et qui ont une chance sur deux d’être corrigées sous une application synchrone de la règle locale. Un inconvénient lié au synchronisme peut être évité en introduisant de l’asynchronisme, c’est à dire en supposant que les cellules ne mettent pas à jour leur état toutes en même temps. On peut, par exemple, supposer que deux cellules adjacentes ne seront jamais actualisées simultanément, ou encore attribuer à chaque cellule une certaine probabilité d’être mise à jour.

* L'application de la dernière condition non seulement laisse la cellule concernée en erreur mais, de plus chaque cellule parmi ces cellules nord, sud, est et ouest a une probabilité de 1/4 d'être erronée.

Pour synthétiser le comportement global de cet automate cellulaire, on a :

1. Les états en erreur qui se corrigent à la prochaine itération de l'automate.

2. Les états en erreur qui admettent un choix de correction valide mais qui avec une probabilité strictement positive peuvent rester en erreur.

3. Les états en erreur qui sont incorrigibles par la règle locale à un moment donné.

Une telle diversité sur le comportement de F est obtenue grâce à l'aléa autorisé sur la règle locale. On verra plus tard la liaison directe qui existe entre le temps de correction et le choix aléatoire de la valeur d'une cellule. Pour le moment, on se contente de préciser que l'un des effets de l'aléa sur le comportement global de l'automate cellulaire est dans la redirection aléatoire des erreurs non corrigibles. Dans certains cas, on observe que l'aléa empêche des corrections possibles. Mais à long terme, cela est plus avantageux et nous rapproche des corrections rapidement des configurations entièrement saines. Les propriétés et les démonstrations qui seront données à la section 4.3 permettront mieux la compréhension de l'effet de cet aléa présent dans la règle locale.

4.2.2 Quelle mise à jour pour les cellules ?

L'aléa sur la correction isotrope des 4-coloriages ne s'arrête pas au niveau de la règle locale mais il devra obligatoirement être présent dans la nature de la mise à jour des cellules. Pour commencer, on présente dans la figure 4.2 le cas d'une erreur sur deux cellules lignes qui tournera dans une boucle infinie et erronée sous une application déterministe de F.

<figure><img src="image_56.png" /><figcaption>FIGURE 4.2 – Erreur infinie sous une application déterministe de F.</figcaption></figure>

Dans toute la suite, on suppose que chaque cellule a une probabilité de 1/2 pour être mise à jour.
Un tel choix pour l'aléa sur les cellules est à notre avis idéal pour briser le type d'erreur présenté
dans la figure 4.2. En effet, toute probabilité prise dans l'intervalle $[0, 1[$ permettra une correction
par l'automate cellulaire avec un temps de correction, qui varie selon cette probabilité.

## 4.3 Analyse de la règle corrigeant les 4-coloriages

Cette section présente une première analyse de la règle probabiliste présentée dans la réf. [6].
Nous mettons en évidence certains éléments indiquant la correction des erreurs dans certaines
situations. On commence par donner une caractérisation globale des motifs corrects et de ceux
responsables de la consommations des erreurs. Pour cela, on partage les zones saines en deux
catégorie, des zones qu'on appellera des zones avec des diagonales et d'autres sans diagonales.
Ensuite, nous enchaînerons avec les différentes propriétés rencontrées lors de notre analyse.

### 4.3.1 Caractérisation des motifs sains des 4-coloriages

Sans perte de généralité, on suppose que l'origine du 3 × 3-motif est l'état 0. La présence de deux valeurs égales sur le voisinage de von Neuman est signalée par deux états 1 sur ce dernier. De même la présence de deux valeurs différentes sur ce voisinage est représentée par deux états 1 et 2. Suivant le même raisonnement, on en déduit que la présence des états 1, 2 et 3 sur ce voisinage reflète l'existence de trois cellules dont les valeurs sont différentes deux à deux.

**Définition 9** Une cellule saine donnée est dite diagonale si au moins l'une des conditions suivantes est satisfaite :

1. L'état nord est égal à l'état est.

2. L'état est égal à l'état sud.

3. L'état sud est égal à l'état ouest.

4. L'état ouest est égal à l'état nord.

Comme chaque cellule saine construite sur l'alphabet $\mathcal{A}$ admet au moins deux états 1 dans son voisinage 1, alors suivant la position de ces deux 1, on en déduit que chaque cellule soit est diagonale ou non-diagonale. La figure 4.3 illustre les différents cas possibles des diagonales, elle est obtenue en considérant toutes les positions possibles des deux états 1 autour de ce voisinage formant une diagonale. Tandis que la figure 4.4 représente les motifs qui n'ont aucune diagonale, également construite en positionnant les états 1 suivant leurs positions possibles de sorte à ne pas former de diagonale. Les cellules blanches de la figure 4.3 peuvent être complétées avec un état de $\{1, 2, 3\}$ tandis que celles de la figure 4.4 peuvent avoir soit 2 soit 3 comme état.

<figure><img src="image_57.png" /><figcaption>FIGURE 4.3 – Les diagonales des motifs sains sur $\mathcal{A}$.</figcaption></figure>

<figure><img src="image_58.png" /><figcaption>FIGURE 4.4 – Les motifs sains sur $\mathcal{A}$ sans diagonale.</figcaption></figure>

<footnote n="1">1. Toute cellule saine sur $\mathcal{A}$ est une cellule qui admet au moins deux valeurs qui sont égales sur son voisinage de von Neuman.</footnote>
**Notation 7**

* Soit $v = ab \in \mathcal{A}^{1 \times 2}$ un motif tel que $a \neq b$, on appelle $v' = ba$ le permuté de $v$.

* Soit $n \in \mathbb{N}$, un motif $v$ est dit motif ligne si $v \in \mathcal{A}^{1 \times n}$ et dit motif colonne si $v \in \mathcal{A}^{n \times 1}$.

* Soit $v \in \mathcal{A}^{1 \times n'}$ un motif ligne, le transposé de $v$ est un motif colonne $v^\top \in \mathcal{A}^{n \times 1}$ tel que :

$$n = n' \text{ et } \forall i \in \{0, \dots, n-1\} : v_{(i,0)}^{\top} = v_{(0,i)}$$

* Soient $P \in \mathcal{A}^{n \times m}$ et $P' \in \mathcal{A}^{n' \times m'}$ deux motifs de taille finie. On dit que $P$ est un sous-motif de $P'$ si

$$n \le n', m \le m' \text{ et } P \subset P'$$

**Propriétés 1** Soit $\mathcal{L}$ un motif sain. On suppose que $\mathcal{L}$ est de taille $n \times n$ avec $n \in \mathbb{N}$. Si aucune cellule de $\mathcal{L}$ n'est diagonale alors $\mathcal{L}$ satisfait les propriétés suivantes :

1. Soit $v = abca$ avec $a, b, c \in \mathcal{A}$ où $a \neq b, a \neq c, b \neq c$. $\mathcal{L}$ n'a aucune occurrence d'un motif $v \in \mathcal{A}^{1 \times 4}$ et de son transposé $v^\top \in \mathcal{A}^{4 \times 1}$

2. La région $\mathcal{L}$ admet l'une des caractérisations suivantes :

(a) Les lignes et les colonnes de $\mathcal{L}$ sont deux à deux égales.

(b) $\mathcal{L}$ admet des lignes qui sont deux à deux égales et des colonnes qui sont la concaténation infinie d'un motif $v^\top$ de longueur 2 et que pour tout $i \in \mathbb{Z}$, si $v^\top$ est le motif formant la colonne $i$ alors tout motif formant une colonne $i+2k$ avec $k \in \mathbb{Z}$ soit égale à $v^\top$ ou au permuté de $v^\top$.

(c) $\mathcal{L}$ admet des colonnes qui sont deux à deux égales et des lignes qui sont la concaténation infinie d'un motif $v$ de longueur 2 et que pour tout $i \in \mathbb{Z}$, si $v$ est le motif formant la ligne $i$ alors tout motif formant une ligne $i+2k$ avec $k \in \mathbb{Z}$ soit égale à $v$ ou au permuté de $v$.

**Preuve.**

1. Par l'absurde, on suppose qu'il existe un motif $v$ de la forme $abca$ avec $a, b, c \in \mathcal{A}$ qui soit un sous-motif de $\mathcal{L}$. Sans perte de généralité, on suppose que $a = 0, b = 1, c = 2$ et que le motif $v$ est en position $(i, j) \in \mathbb{Z}^2 \subset [0, n] \times [0, n]$. Les cellules en position $(i+1, j-1)$ et $(i+2, j-1)$ appartiennent à $\mathcal{L}$ donc sont saines et sans diagonales. L'état est donc 3. Ceci mène à une contradiction car la cellule $(i+2, j-1)$ est soit saine soit une diagonale. Le cas des motifs $v^\top$ se déduit par symétrie en utilisant l'isotropie de F.

2. On démontre la seconde propriété par construction. Considérons une cellule saine sans diagonale ayant 0 comme état et qui est en position (0,0). Sans perte de généralité, cette dernière admet uniquement deux états 1 que l'on peut poser verticalement, i.e, nord = sud = 1. (Le cas où les états 1 sont superposés horizontalement se déduit avec les mêmes arguments par symétrie de la règle locale.)

Les cellules est et ouest sont alors soit égales (figure 4.5b) soit différentes (figure 4.5a).

<figure><img src="image_59.png" /><figcaption>(a) Cas 1 d'une cellule sans diagonale.</figcaption></figure>

<figure><img src="image_60.png" /><figcaption>(b) Cas 2 d'une cellule sans diagonale.</figcaption></figure>

FIGURE 4.5 – Illustration 1 pour la preuve 4.3.1.

En complétant les deux motifs de façon à rester sain et sans diagonales. On obtient les deux motifs suivants :
<figure><img src="image_61.png" /><figcaption>(a) Cas 1 complété en 3 × 3.</figcaption></figure>

<figure><img src="image_62.png" /><figcaption>(b) Cas 2 complété en 3 × 3.</figcaption></figure>

FIGURE 4.6 – Illustration 2 pour la preuve 4.3.1.

Traitons chaque cas séparément :

* **Cas 1** : Par construction, l'unique possibilité pour avoir des cellules saines et qui ne forment pas de diagonales entre elles impose que les cellules se trouvant en position $[-1, 1] \times \{j\}$ avec $j \le 2$ soient égales à 203 si $j$ est pair et à 312 si $j$ est impair. Par récurrence, on construit les colonnes à droite de ce motif une à une. Commençons par l'affectation des valeurs aux cellules en positions $\{2\} \times [-\infty, 1]$. La cellule en position (2, 1) a pour valeur $a \in \{0, 1\}$. Par conséquent, la cellule en position (2, 0) a pour valeur $b$ tel que $b \in \{0, 1\} \setminus \{a\}$. De là, on déduit que la colonne en position $\{2\} \times [-\infty, 1]$ est la concaténation verticale et infinie du motif $01^\top$ ou $10^\top$. Par induction, on en déduit que toutes les colonnes à droite de ce motif sont des concaténations infinie des $01^\top$ ou $10^\top$ si la colonne est en position paire sinon est la concaténation infinie des $23^\top$ ou $32^\top$. (voir la figure 4.7).

<figure><img src="image_63.png" /><figcaption>FIGURE 4.7 – Illustration complète du cas 1.</figcaption></figure>

On en déduit donc que la région $\mathcal{L}$ admet des lignes qui sont deux à deux égales et des colonnes qui sont la concaténation infinie d'un motif $v^\top$ de longueur 2 et que pour tout $i \in \mathbb{Z}$, si $v^\top$ est le motif formant la colonne $i$ alors tout motif formant une colonne $i+2k$ avec $k \in \mathbb{Z}$ est soit égale à $v^\top$ soit le permuté de $v^\top$. Ceci implique le cas (2.b). Le cas (2.c) se déduit par l'isotropie de la règle locale.

* **Cas 2** : Par hypothèse la valeur des cellules en positions $(0, -2)$, $(0, 2)$ sont soit 0 soit 2 tandis que la valeur des cellules en positions $(-2, 0)$, $(2, 0)$ sont soit 0 soit 1. Si l'une de ces quatre dernières cellules a une valeur différente de 0 alors sa cellule adjacente satisfera la cas 1 précédent. Ce qui fait qu'on suppose que les quatre cellules sont associées à la valeur 0. La figure 4.8 représente le motif $3 \times 3$ du cas 2 complété en un motif de taille $5 \times 5$.

En généralisant ce raisonnement, on déduit que si toutes les cellules de $\mathcal{L}$ satisfont uniquement le cas 2 alors toutes ses lignes et ses colonnes sont deux à deux égales.

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

**Remarque 12** Les propriétés données précédemment restent valides si la taille de $\mathcal{L}$ est infinie.
<figure><img src="image_65.png" /><figcaption>FIGURE 4.8 – Cas 2 complété en 5 × 5.</figcaption></figure>

4.3.2 Correction de deux cellules adjacentes dans une région à diagonales

Dans cette partie, nous étudions la correction de deux cellules en erreur adjacentes avec des mises à jour $\frac{1}{2}$-asynchrone. Comme l'automate cellulaire est isotrope, on peut, sans perte de généralité, étudier le cas de deux cellules lignes et le cas des erreurs colonnes se déduira par symétrie.

**Notation 8** On dit que deux cellules lignes sont des diagonales si chacune des deux cellules est une diagonale. Autrement dit, si elles vérifient l'un des cas présentés dans la figure 4.9 où a, b, c $\in \mathcal{A}$ tels que a, b, c sont deux-à-deux différents.

<figure><img src="image_66.png" /><figcaption>FIGURE 4.9 – Cas possibles de deux cellules adjacentes et diagonales.</figcaption></figure>

**Proposition 7** Sous des mises à jour $\frac{1}{2}$-asynchrones, deux cellules adjacentes, erronées, diagonale et entourées par des cellules saines sont corrigibles par F presque sûrement.

**Remarque 13** La démonstration de la proposition 7 sera faite suivant les cas présentés dans la figure 4.9. On observe que les cas présentés dans la figure 4.9a, 4.9f et 4.9h sont des cas particuliers du cas donné dans la figure 4.9e. De même, les cas présentés dans la figure 4.9g et 4.9i sont des cas particuliers du cas donné dans la figure 4.9d.

Également, les cas donnés dans 4.9d, 4.9b et 4.9e, 4.9c sont respectivement des symétriques et possèdent les mêmes propriétés par l'application de F. Pour cela, la preuve de la proposition qui suit sera réduite aux deux cas présentés dans la figure 4.9c et 4.9e.

Preuve.

* Considérons deux cellules lignes erronées à diagonales satisfaisant le cas présenté dans la figure 4.9e. Sans perte de généralité, on suppose que $b = 0$. Nous allons discuter les cas en fonction des valeurs de a, c $\in \{1, 2, 3\}$.

1. Si $a \neq c$ :

Sans perte de généralité, on suppose que $a = 1$ et $c = 2$ et on nomme les deux cellules restantes par $d$ et $e$ comme présenté dans la figure 4.10. On a $d \in \{1, 3\}$ et $e \in \{2, 3\}$.
<figure><img src="image_67.png" /><figcaption>FIGURE 4.10 - Cas où $a \neq c$.</figcaption></figure>

* Si $d = 1$ et $e = 2$ alors les nouveaux états possibles pour les deux cellules en erreur sont $\{01,21,31,03,23,33,00,20,30\}$. Ces états sont retrouvés en combinant les aléas présents dans la règle locale avec ceux dû à la nature des mises à jour où chaque cellule a une chance sur deux d'être changée. Ce qui fait que l'une des cellules (celle à la gauche) a une probabilité $\frac{1}{2}$ de rester un 0 et a une probabilité de $\frac{1}{4}$ de prendre une valeur parmi $\{2,3\}$ tandis que l'autre (celle à la droite) a une probabilité de $\frac{1}{4}$ d'avoir l'une des valeurs parmi $\{1,3\}$ et une probabilité de $\frac{1}{2}$ de rester fixe. Comme les cellules qui entourent les deux cellules en erreur sont saines alors ces dernières ont une probabilité de $\frac{5}{16}$ de rester en erreur. Ce qui fait que si le voisinage sain n'est pas perturbé sous les itérations de F alors on en déduit que dans ce cas les deux cellules erronées seront corrigées presque sûrement, étant donnée, que à chaque itération $n \in \mathbb{N}$, les deux cellules ont une probabilité de $(\frac{5}{16})^n$ de rester en erreur. Ce dernier tend vers 0 quand $n$ tend vers l'infini.

* Si $d = 3$ et $e = 2$, le même argument est valide pour $d = 1$ et $e = 3$; donc les nouveaux états possibles pour les cellules en erreur sont $\{00,20,01,21,03,23\}$. On déduit qu'à chaque itération $n \in \mathbb{N}$ de F, les deux cellules ont une probabilité de $(\frac{1}{4})^n$ de rester en erreur.

* Si $d = e = 3$ alors les nouveaux états sont $\{00,20,01,21\}$ et cela donne une probabilité de $(\frac{1}{4})^n$ de rester en erreur à $n^{\text{ième}}$ itération de F.

2. Si $a=c$: on suppose que $a=1$ donc les valeurs des cellules $d$ et $c$ sont $\{2,3\}$.

* Si $d = 2$ et $e = 3$ (même raisonnement pour $d = 3$ et $e = 2$) alors les nouveaux états possibles sont $\{00,02,30,32\}$. On a donc une probabilité de $(\frac{1}{4})^n$ de rester en erreur à l'itération $n^{\text{ième}}$ de F.

* Si $d = e = 2$ alors les nouveaux états possibles sont $\{00,03,30,33\}$, ce qui donne une probabilité de $(\frac{1}{2})^n$ de rester en erreur à l'itération $n^{\text{ième}}$ de F.

* Considérons maintenant le cas de deux cellules lignes erronées satisfaisant le cas donné dans la figure 4.9c. Les valeurs possibles des deux cellules blanches de sorte à avoir des cellules saines et qui ne rentrent pas dans le cas de la figure 4.9e sont $\{21,23,31\}$. Avec le même raisonnement que précédemment, on déduit que si la valeur des deux cellules blanches est 21 alors on a une probabilité de $(\frac{1}{2})^n$ de rester en erreur à la $n^{\text{ième}}$ itération de F, sinon la probabilité est de $(\frac{1}{4})^n$.

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

### 4.3.3 Synthèse

Dans ce chapitre, on a détaillé le comportement de l'automate cellulaire proposé par Fatès, Marcovici et Taati [6] pour une correction probabiliste des 4-coloriages. Notre analyse est basée sur la nature des motifs qui consomment les erreurs, ce qui permet de comprendre la dynamique locale de l'automate et sa capacité à rétablir l'ordre.

Le travail a été mené dans le cadre de la correction de deux cellules en erreur seulement, ce qui a permis d'établir des observations précises sur le rôle des motifs correcteurs et sur la propagation des erreurs. La généralisation à un nombre plus important de cellules en erreur est en cours d'étude, et les résultats préliminaires suggèrent que les mécanismes identifiés restent pertinents, mais nécessitent encore des analyses complémentaires.
**Question 9** Peut-on concevoir un autre automate cellulaire capable de corriger les 4-coloriages, tout en étant associé à une dynamique plus simple que celle de l'automate présenté dans ce chapitre ?
Bibliographie

[1] Robert BERGER. *The Undecidability of the Domino Problem*. T. 66. Memoirs of the American Mathematical Society. Providence, RI : American Mathematical Society, 1966.

[2] Steven CAMAZINE et al. *Self-Organization in Biological Systems*. Princeton, NJ : Princeton University Press, 2001.

[3] C. CHARLES. *Introduction aux problèmes inverses*. Note technique. Sans date indiquée. Université de Liège - Gembloux Agro-Bio Tech, n.d. URL: https://orbi.uliege.be/bitstream/2268/162659/1/2014-1-Pbm_inverses.pdf.

[4] Edsger W. DIJKSTRA. "Self-Stabilization in Spite of Distributed Control". In: *Selected Writings on Computing : A Personal Perspective*. Texts and Monographs in Computer Science. New York, NY : Springer, 1982, p. 223-237. DOI: 10.1007/978-1-4612-5695-3_7.

[5] Nazim FATÈS. "Stochastic Cellular Automata Solutions to the Density Classification Problem - When Randomness Helps Computing". In: *Theory of Computing Systems* 53.2 (2013), p. 223-242. DOI: 10.1007/s00224-012-9386-3.

[6] Nazim A. FATÈS, Irène MARCOVICI et Siamak TAATI. "Cellular Automata for the Self-Stabilisation of Colourings and Tilings". In: *Reachability Problems*. Bruxelles, Belgium, 2019, p. 121-136. DOI: 10.1007/978-3-030-30806-3_10.

[7] H. FUKŚ. "Sequential Cellular Automata for the Density Classification Problem". In: *Complex Systems* 24.3 (2015), p. 199-215. DOI: 10.25088/ComplexSystems.24.3.199.

[8] H. FUKŚ. "Solution of the Density Classification Problem with Two Cellular Automata". In: *Parallel Processing and Applied Mathematics (PPAM 2001)*. T. 2328. Lecture Notes in Computer Science. Springer, 2002, p. 172-178. DOI: 10.1007/3-540-48086-2_18.

[9] Henryk FUKŚ. "Solving Two-Dimensional Density Classification Problem with Two Probabilistic Cellular Automata". In: *Journal of Cellular Automata* 10.1-2 (2015), p. 149-160. URL: https://arxiv.org/pdf/1506.06653.

[10] Péter GÁCS. "Reliable Cellular Automata with Self-Organization". In: *Journal of Statistical Physics* 103.1-2 (2001), p. 45-267. DOI: 10.1023/A:1004823720305.

[11] Peter GÁCS, G. L. KURDYUMOV et Leonid A. LEVIN. "One Dimensional Uniform Arrays That Wash Out Finite Islands". In: *Problems of Information Transmission* 14.3 (1978), p. 223-226. URL: https://cs-web.bu.edu/faculty/gacs/papers/GKL.pdf.

[12] Peter GÁCS et Jürgen REIF. "A Simple Three-Dimensional Real-Time Reliable Cellular Array". In: *Journal of Computer and System Sciences* 36.2 (1988), p. 125-147. DOI: 10.1145/22145.22188.

[13] E. HAIRER, S. P. NØRSETT et G. WANNER. *Solving Ordinary Differential Equations I: Nonstiff Problems*. 2nd ed. T. 8. Springer Series in Computational Mathematics. Springer, 1993. DOI: 10.1007/978-3-540-78862-1.

[14] Marlène HANTZ et Jean-René COURTAULT. *Étude de la robustesse des automates cellulaires bidimensionnels asynchrones*. Rapp. tech. Rapport de recherche. Université de Lorraine, juin 2009.
[15] Stuart A. KAUFFMAN. *The Origins of Order: Self-Organization and Selection in Evolution*. New York, NY: Oxford University Press, 1993.

[16] Hiroaki KITANO. "Biological Robustness". In: *Nature Reviews Genetics* 5.11 (2004), p. 826-837. DOI: 10.1038/nrg1471.

[17] Mark LAND et Richard K. BELEW. "No Perfect Two-State Cellular Automata for Density Classification Exists". In: *Physical Review Letters* 74.25 (1995), p. 5148-5150. DOI: 10.1103/PhysRevLett.74.5148.

[18] Leonid A. LEVIN. *Self-stabilization of Circular Arrays of Automata*. arXiv preprint. 2006. arXiv: cs/0602033 [cs.DM]. URL: https://arxiv.org/abs/cs/0602033.

[19] Irène MARCOVICI et al. "Density Classification on Infinite Lattices and Trees". In: *LATIN 2012: Theoretical Informatics*. Sous la dir. de David FERNANDEZ-BACA. T. 7256. Lecture Notes in Computer Science. Arequipa, Peru: Springer, 2012, p. 109-120. URL: https://hal.scienceshal-00712614.

[20] Alexander MORDVINTSEV, Eero NIKLASSON et Michael LEVIN. "Growing Neural Cellular Automata". In: *arXiv preprint arXiv:2006.09661* (2020). URL: https://arxiv.org/abs/2006.09661.

[21] Nicholas PIPPENGER. "Symmetry in Self-Correcting Cellular Automata". In: *Journal of Computer and System Sciences* 49.1 (1994), p. 83-95. DOI: https://doi.org/10.1016/S0022-0000(05)80087-X.

[22] K. K. POKKULURI et B. SUBRAMANI. "Cellular Automata and Its Applications in Protein Bioinformatics". In: *International Journal of Engineering Research and Technology (IJERT)* 3.6 (2014), p. 1347-1350.

[23] M. REDEKER. "Density Classification Quality of the Traffic-Majority Rules". In: *arXiv preprint arXiv:1409.3588* (2014). URL: https://arxiv.org/abs/1409.3588.

[24] Steven H. STROGATZ. *Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry, and Engineering*. Boca Raton, FL: CRC Press, 2018.

[25] S. TAATI. "Two-Dimensional Traffic Rules and the Density Classification Problem". In: *Cellular Automata — 12th International Conference on Cellular Automata for Research and Industry (ACRI 2016)*. T. 9863. Lecture Notes in Computer Science. Springer, 2016, p. 123-134. DOI: 10.1007/978-3-319-39300-1_11.

[26] Albert TARANTOLA. *Inverse Problem Theory and Methods for Model Parameter Estimation*. SIAM, 2005.

[27] A. L. TOOM. "Stable and Attractive Trajectories in Multicomponent Systems". In: *Multicomponent Random Systems*. Sous la dir. de R. L. DOBRUSHIN et Y. G. SINAI. Marcel Dekker, 1980, p. 549-575.

[28] Rodney WHITE et Geoffry ENGELEN. "Cellular Automata and Fractal Urban Form: A Cellular Modeling Approach to the Evolution of Urban Land-Use Patterns". In: *Environment and Planning A* 25.8 (1993), p. 1175-1199. DOI: 10.1068/a251175.

[29] Stephen WOLFRAM. *A New Kind of Science*. Champaign, IL: Wolfram Media, 2002.

[30] Stephen WOLFRAM. "Cryptography with Cellular Automata". In: *Advances in Cryptology — CRYPTO' 85*. T. 218. Lecture Notes in Computer Science. Springer, 1986, p. 429-432. DOI: 10.1007/3-540-39799-X_35.

[31] Kemin ZHOU, John C. DOYLE et Keith GLOVER. *Robust and Optimal Control*. Upper Saddle River, NJ: Prentice Hall, 1996.