Automates cellulaires 

Télécharger le fichier original (Mémoire de fin d’études)

Discussion et propriétés

L’objet principal d’étude de cette thèse est l’ensemble des évolutions des automates cellulaires. Aussi, l’objet qui nous intéresse réellement n’est pas l’automate cellulaire mais le système dynamique constitué de l’ensemble des configurations et de la règle globale d’évolution. Nous discutons donc les conditions syntaxiques nécessaires et suffisantes pour que deux automates cellulaires aient un même ensemble d’évolutions. Enfin nous présentons quelques variantes et propriétés rattachées à ces définitions.
FIG. 1.1 – Exemples de diagrammes espace-temps partiels Forme syntaxique
La définition choisie pour les automates cellulaires fait certains choix de représentation.
Nous discutons leurs variantes et leurs implications.
Voisinage. Le voisinage est défini comme un ensemble ordonné de vecteurs de déplacement dans la grille. Le choix d’un ordre sur les vecteurs de voisinage est un outil pour définir l’application de la règle locale de transition mais n’a pas d’incidence sur les évolutions de l’automate cellulaire.
◮ En effet, soit A un automate cellulaire de dimension d et de voisinage {v1, . . . , vν }. Soit τ une permutation de J1, νK. L’automate cellulaire Aτ défini par Zd, QA, vτ (1), . . . , vτ (ν) , δτ , avec pour règle locale de transition δτ : (x1, . . . , xν ) δA(xτ −1 (1), . . . , xτ −1 (ν)), a même règle globale de transition que A (I.E. GA = GAτ ).
Implicitement, on travaillera toujours à réordonnement des voisins près et on désignera parfois par voisinage l’ensemble des vecteurs de voisinage, indépendamment de l’ordre.
Le voisinage d’un automate cellulaire peut être augmenté sans changer la règle globale de transition. Il suffit d’ignorer les dépendances ajoutées.
◮ Formellement, soit A un automate cellulaire de dimension d et de voisinage {v1, . . . , vν }. Soit
v un vecteur de voisinage tel que v n’appartienne pas au voisinage de A (I.E. v VA). L’automate cellulaire Av défini par Zd, QA, {v1, . . . , vν , v} , δv , avec pour règle locale de transition δv : (x1, . . . , xν+1) δA(x1, . . . , xν ), a même règle globale de transition que A (I.E. GA = GAv ).
Inversement, on peut supprimer les vecteurs de voisinages inutiles. En fait, étant don-née une règle globale de transition d’automate cellulaire G, il existe – à réordonnement des vecteurs de voisinage près – un unique automate cellulaire A dont le voisinage est minimal au sens de l’inclusion et dont la règle globale de transition est G.
◮ En effet, soit B un automate cellulaire de dimension d dont la règle globale de transition est G et soit {v1, . . . , vν } son voisinage. Un vecteur de voisinage vi est utile s’il existe un (ν − 1)-uple d’états (x1, . . . , xν−1) de B et deux états x et y de B tels que δ(x1, . . . , xi−1, x, xi, . . . , xν−1) = δ(x1, . . . , xi−1, y, xi, . . . , xν−1) .
L’ensemble des vecteurs de voisinage utiles {vi1 , . . . , vik } est le voisinage minimal de G. Soit q un état de B. L’automate cellulaire A est alors défini par Zd, Q B , {v i1 , . . . , v } , (x , . . . , x ) δ B (y 1 , . . . , y ) où yj est égal à xl si vj est un vecteur utile vil et à q sinon.
Implicitement, on associera toujours à une règle globale de transition l’automate cellulaire dont le voisinage est minimal. Une notion très pratique est celle de rayon de voisinage. On appelle rayon de voisinage d’un automate cellulaire A, noté rA, le maximum des normes infinies de ses vecteurs de voisinages (i.e. rA = max { v ∞}v∈VA ). Par extension, on appelle rayon de voisinage minimal le rayon de voisinage de l’automate cellulaire réalisant le voisinage minimal.
Pour clore ce paragraphe consacré aux voisinages, la table 1.1 présente quelques voisinages classiques dont certains sont représentés sur la figure 1.2. À partir de la dimension 2, la notion de voisinage unidirectionnel est ambiguë, nous choisissons ici un voisinage inspiré par le voisinage de Moore.
Automates cellulaires partitionnés. Au lieu de transmettre tout son état à chacun de ses voisins, une cellule d’un automate cellulaire partitionné envoie un message différent à chaque voisin. L’ensemble d’états est un produit cartésien d’ensembles de messages. Chaque cellule commence par envoyer le i-ème message, la i-ème composante de son état, à la cellule dont elle est le i-ème voisin. Puis, une fois tous les messages expédiés, le nouvel état est calculé en fonction de tous les messages reçus. La règle locale de transition se décompose donc en une étape d’échange de messages et une étape de calcul.
Un automate cellulaire partitionné A est un quadruplet Zd, ν i=1 Qi, {v1, . . . , vν } , ψ où les Qi sont des ensembles finis de messages, les vi sont des vecteurs de voisinage et ψ est une application de ν i=1 Qi dans lui-même. L’automate cellulaire classique associé à A est Zd, ν , . . . , vν } , δ où δ est défini pour tout ν-uple d’états x(1), . . . , x(ν) i=1 Qi, {v1 par δ(x(1), . . . , x (ν)) = ψ(x (1)1, . . . , x(νν)) où x(ii) désigne le i-ème message du i-ème voisin. La règle globale de transition de A se décompose naturellement en une étape de transmission de messages suivie d’une étape de calcul ψ ◦ (σ−v1 × • • • × σ−vν ) .
Automates cellulaires polynomiaux. En choisissant comme ensemble d’états une structure algébrique particulière et en prenant comme règle locale de transition une opération sur cette structure, on définit des automates cellulaires pour lesquels on espère pouvoir prédire plus de propriétés. Ainsi les automates cellulaires polynomiaux sont définis par une règle locale de transition polynomiale sur un anneau commutatif fini.
Un automate cellulaire polynomial A est un quadruplet Zd, (Q, +, ×) , V, P où V est un voisinage et P un polynôme en |V | variables sur l’anneau commutatif fini (Q, +, ×). L’automate cellulaire classique associé à A est Zd, Q, V, δ où δ est défini pour tout νuple d’états (x1, . . . , xν ) par δ(x1, . . . , xν ) = P (x1, . . . , xν ).
Deux cas particuliers d’automates cellulaires polynomiaux seront étudiés dans cette thèse. Un automate cellulaire linéaire est un automate cellulaire polynomial dont le polynôme est de degré au plus un. Un automate cellulaire bilinéaire est un automate cellulaire polynomial dont le polynôme est composé uniquement de monômes de degré deux.
Évolution
L’ensemble des règles globales de transition des automates cellulaires est en bijection avec l’ensemble des automates cellulaires de voisinage minimal (quotienté par les permutations des vecteurs de voisinage). Nous discutons maintenant des variantes et propriétés des évolutions des automates cellulaires.
Configurations. En toute généralité, une configuration d’un automate cellulaire est infinie et non récursive donc pour nous inaccessible. Aussi est-il courant d’étudier la dynamique des automates cellulaires restreinte à des familles de configurations closes par application de la règle globale de transition et dont les diagrammes espace-temps sont raisonnablement représentables. Configurations finies. Historiquement, les automates cellulaires ont souvent été étudiés sur les configurations finies1. Soit A un automate cellulaire de dimension d et q un état quiescent de A (i.e. vérifiant δA(q, . . . , q) = q). Une configuration q-finie C de A est une configuration q-monochromatique sauf sur un support fini. Formellement, C vérifie ∃r ∈ N, ∀p ∈ Zd, p ∞ r ⇒ Cp = q .
On notera GF la restriction d’une règle globale de transition G aux configurations q-finies lorsque q est connu ou lorsque le choix de q est laissé libre.
Configurations périodiques. Dans cette thèse, en dimension d, on s’intéressera principalement aux configurations périodiques possédant d vecteurs de périodicité indépendants. Soit A un automate cellulaire de dimension d. Une configuration périodique C de A, de période π ∈ N, vérifie ∀p ∈ Zd, ∀v ∈ J−1, 1Kd, Cp+πv = Cp .
On notera GP la restriction d’une règle globale de transition G aux configurations périodiques. L’image par GP d’une configuration périodique est une configuration périodique de période inférieure ou égale car l’automate cellulaire, de par sa définition uniforme, est incapable de briser la symétrie créée par la périodicité.
Configurations ultimement périodiques. Beaucoup moins répandues dans la littérature, les configurations ultimement périodiques représentent un compromis entre les deux types de configurations précédents. Soit A un automate cellulaire de dimension d. Une configuration ultimement périodique C de A, de période π, est une configuration périodique sauf sur un support fini. Formellement, elle vérifie ∃r ∈ N, ∀p ∈ Zd, ∀v ∈ J−1, 1Kd, ( p ∞ r ∧ p + πv ∞ r) ⇒ Cp = Cp+πv .
On notera GU la restriction d’une règle globale de transition G aux configurations ultimement périodiques. Pour les mêmes raisons que ci-dessus, l’image par GU d’une configuration ultimement périodique est une configuration ultimement périodique de période inférieure ou égale. Configurations univers. Cette dernière famille de configurations est différente des précédentes. Elle n’est pas stable par application d’une règle globale de transition mais ces configurations possèdent des propriétés combinatoires intéressantes : elles contiennent tous les motifs finis possibles. Soit A un automate cellulaire de dimension d. Une configuration univers C de A est une configuration vérifiant ∈ QA , ∀r ∈ N, ∃p ∈ Z , ∀v ∈ J−r, rK , Cp+v = Cv
En particulier, si on connaît l’ensemble d’états d’un automate cellulaire A et un couple (C, GA(C)) formé d’une configuration univers et de son image par GA, alors on peut déterminer A.
◮ En effet, on sait que tout motif fini apparaît dans C et que A possède un rayon de voisinage minimal. Pour trouver ce dernier, il suffit de trouver le plus petit r vérifiant ∀p, p′ ∈ Zd, (∀v ∈ J−r, rKd, Cp+v = Cp′+v ) ⇒ GA(C)p = GA(C)p′ .
Puisque l’image d’un motif de rayon r n’est pas influencée par les états à l’extérieur du motif, r est un rayon de voisinage acceptable pour A. Il suffit ensuite de construire δ en regardant l’image de chaque motif. L’universalité de C assure que tous les motifs sont présents.
Règle globale de transition. Nous explorons maintenant quelques propriétés classiques des règles globales de transition qui nous seront utiles par la suite.
Caractérisation topologique. Un résultat fondamental est la caractérisation to-pologique des automates cellulaires introduite par G. Hedlund [19] et redécouverte indépendamment par D. Richardson.
On munit QZd de la topologie produit, sur Zd, de la topologie triviale sur Q. On obtient ainsi un espace métrique compact. La translation de vecteur v ∈ Zd sur QZd est l’application σv , bijective et continue, de QZd dans lui-même qui à une configuration C associe la configuration σv (C) vérifiant, en toute position p ∈ Zd, l’égalité σv (C)p+v = Cp.
Théorème 1 (G. Hedlund [19]). Soit Q un ensemble fini. Une application de QZd dans lui-même commutant avec les translations est continue si et seulement si elle est la règle globale de transition d’un automate cellulaire.
◮ Pour une démonstration rapide et élégante, le lecteur est renvoyé à la thèse de B. Durand [7]. L’idée de la preuve est de remarquer que les ensembles de configurations de la forme Op,r (C) = C ′ Zd d , v ′ ∈ Q | ∀v ∈ Z ∞r ⇒ Cp+v = Cp+v forment une base d’ouverts pour QZd .
Ce résultat permet de s’affranchir un peu plus de la définition syntaxique des automates cellulaires. En particulier, il permet de vérifier rapidement que certaines compositions de fonctions correspondent à des automates cellulaires. D’autre part, l’espace étant compact, on en déduit que si une règle globale de transition d’un automate cellulaire est bijective, alors cet automate cellulaire est réversible : il existe un automate cellulaire dont la règle globale de transition est l’inverse de la première.
Pour simplifier l’écriture, nous nous permettons à partir de maintenant de confondre parfois l’automate cellulaire et sa règle globale de transition. Par exemple, on parlera d’automate cellulaire injectif pour désigner un automate cellulaire dont la règle globale de transition est injective. Propriétés immédiates. Par propriétés immédiates, il faut entendre les propriétés observables en ne regardant qu’un pas de calcul (i.e. en étudiant l’image de G). Ces propriétés ont été étudiées en détail dans la littérature.
La surjectivité des automates cellulaires a été reliée à l’injectivité sur les configurations finies par E. F. Moore et J. Myhill par un théorème connu sous le nom de théorème des jardins d’Eden. Dans sa formulation originelle, il concerne uniquement les automates cellulaires possédant un état quiescent. On appelle jardin d’Eden une configuration qui n’est pas accessible par la règle globale de transition : on peut la quitter mais on ne peut y accéder. Cette notion de jardin d’Eden amène naturellement à l’idée d’ensemble limite que nous étudierons au paragraphe suivant.
Théorème 2 (E. F. Moore [16] et J. Myhill [17]). Un automate cellulaire est surjectif si et seulement si il est injectif sur les configurations finies.
On notera que ce résultat admet une variante faible pour les automates cellulaires sans état quiescent. En effet, pour tout automate cellulaire de règle globale de transition G il existe une puissance Gk de cette règle globale qui possède un état quiescent q.
◮ Pour s’en convaincre, il suffit de considérer l’action de G sur les configurations monochromatiques. Pour tout état q, notons q la configuration q-monochromatique. Un automate cellulaire étant défini uniformément, il ne peut rompre la symétrie d’une configuration monochromatique. Pour tout état q, il existe un état q′ tel que G(q) = q′. L’ensemble des états étant fini, il existe au moins un cycle de configurations monochromatiques. Soit k la longueur d’un tel cycle et q une configuration du cycle. Alors, Gk (q) = q donc q est quiescent pour Gk .
Du théorème précédent on déduit que Gk est surjective si et seulement si elle est injective sur les configurations finies. Or, G est surjective (respectivement injective) si et seulement si Gk l’est. On en déduit que G est surjective si et seulement si Gk est injective sur les configurations finies.
Du théorème précédent on conclut que les automates cellulaires injectifs sont objectifs. En raison de la remarque précédente, ce résultat est valide pour tous les automates cellulaires, avec ou sans état quiescent.
Corollaire 1. La règle globale de transition d’un automate cellulaire est injective si et seulement si elle est bijective.
Ces propriétés immédiates fournissent des exemples simples de propriétés globales des automates cellulaires qui ne sont pas locales. En effet, si S. Amoroso et Y. N. Patt [23] ont montré que ces propriétés étaient décidables en dimension 1, J. Kari [52] a montré qu’elles étaient indécidables dès la dimension deux. Ce résultat montre aussi que le comportement des automates cellulaires est plus compliqué en dimension deux qu’en dimension un.
Théorème 3 (S. Amoroso et Y. N. Patt [23]). L’injectivité et la surjectivité des automates cellulaires de dimension un sont décidables.
La démonstration de ce théorème repose sur l’étude de transducteurs réalisant une transition de l’automate cellulaire. Par un argument de combinatoire des mots, on ra-mène la décidabilité de la propriété à l’étude des images d’un ensemble de mots finis. K. Sutner [43] a proposé un algorithme en temps quadratique pour résoudre ce problème. Cette construction ne se généralise pas à la dimension deux.
Théorème 4 (J. Kari [52]). L’injectivité et la surjectivité des automates cellulaires de dimension deux sont indécidables.
La démonstration de ce théorème procède par réduction au problème de pavabilité du plan par un jeu de tuiles de Wang et aux pavages apériodiques introduits par R. Robinson [21]. Une conséquence de ce résultat est qu’il n’existe pas de méthode efficace pour énumérer ces automates cellulaires. Il n’existe pas de fonction récursive reliant le rayon minimal de voisinage d’un automate cellulaire réversible à celui de son inverse.
Dans ce contexte, les automates cellulaires partitionnés ont un meilleur comportement : un automate cellulaire partitionné Zd, ν Qi, {v1, . . . , vν } , ψ est bijectif si et seulement si ψ est bijective.
◮ En effet, la règle globale de transition G de cet automate partitionné peut se décomposer en −1 −1 −1 ν Zd ψ ◦ où ψ est l’extension canonique de ψ à ( et où les σv1 × σv2 × • • • × σvν i=1 Qi) σv−i1 ont pour ensemble d’états Qi. Un produit de translations étant bijectif et continu, la règle globale de transition est bijective si et seulement si ψ l’est.
Ce résultat peut sembler contredire l’indécidabilité de la bijectivité à partir de la dimension 2 mais il n’en est rien. En effet, s’il est possible de simuler simplement tout automate cellulaire par un automate cellulaire partitionné et tout automate cellulaire bijectif par un automate cellulaire partitionné bijectif, il n’existe pas de transformation récursive qui à un automate cellulaire associe un automate cellulaire partitionné tel que le premier soit bijectif si et seulement si le second l’est. La figure 1.3, extraite de la thèse de B. Durand [7], résume les implications connues entre les propriétés immédiates sur les différentes familles de configurations.
Propriétés asymptotiques. À l’opposé des propriétés immédiates, on trouve les propriétés asymptotiques qui concernent le comportement à très long terme des automates cellulaires. On s’intéresse aux configurations qui peuvent apparaître à n’importe quel instant dans un comportement de l’automate cellulaire
Les automates nilpotents semblent avoir un comportement très simple : la configuration devient homogène en un temps borné. Cependant, ce temps n’est pas bornable récursivement en la taille de l’automate cellulaire. En effet, K. Čulik II, J. Pachl et S. Yu [38] ont montré que cette propriété est indécidable en dimension deux. Ce résultat a été étendu à la dimension un par J. Kari [44] exhibant ainsi une propriété globale simple mais indécidable des automates cellulaires de dimension un.
Théorème 5 (K. Čulik II, J. Pachl et S. Yu [38]). La nilpotence des automates cellulaires de dimension deux est indécidable.
Théorème 6 (J. Kari [44]). La nilpotence des automates cellulaires de dimension un est indécidable.
La démonstration procède ici aussi par réduction à un problème de pavabilité. Généralisant ce résultat, J. Kari [53] a démontré un analogue du théorème de Rice pour les propriétés des ensembles limite des automates cellulaires : toute propriété non triviale concernant les ensembles limite est indécidable. Un résultat du même type a récemment été proposé par J. Cervelle.
La notion de convergence vers un point fixe peut être adaptée à d’autres familles de configurations comme les configurations périodiques. K. Sutner a montré que la convergence de toutes les configurations périodiques vers un point fixe est indécidable.
Théorème 7 (K. Sutner [42]). Savoir si toutes les configurations périodiques d’un automate cellulaire de dimension un évoluent vers un point fixe est indécidable.
Ce résultat, obtenu par simulation de machines de Turing sur automate cellulaire, a été généralisé par J. Mazoyer et I. Rapaport [70] au cas où toutes les configurations périodiques atteignent un même point fixe en utilisant une réduction à un problème de pavabilité. Nous parlerons alors de nilpotence par analogie avec le cas général. Un automate cellulaire A est nilpotent pour les configurations périodiques s’il existe une configuration périodique C telle que, pour toute configuration périodique C′, il existe un temps t tel que GtA(C′) = C. La configuration C est nécessairement monochromatique.
Théorème 8 (J. Mazoyer et I. Rapaport [70]). La nilpotence des automates cellu-laires de dimension un sur les configurations périodiques est indécidable.
Dans le cas de la nilpotence, il est facile de montrer qu’un automate cellulaire est nil-potent : il suffit d’exhiber une borne T pour la transitoire (i.e. telle que GT soit constante). Dans le cas de la nilpotence sur les configurations périodiques, il est facile de montrer qu’un automate cellulaire n’est pas nilpotent sur les configurations périodiques : il suffit d’exhiber un cycle non q-monochromatique (i.e. une configuration périodique C, distincte GA×B =γ◦(GA×GB)◦γ de q en 0 et une durée T telle que GT (C) = C). L’ensemble des automates cellulaires nilpotents est récursivement énumérable alors que l’ensemble des automates cellulaires nilpotents pour les configurations périodiques est co-récursivement énumérable.

Une caractérisation par clôture

Si la caractérisation topologique des automates cellulaires de G. Hedlund et D. Ri-chardson permet de composer des automates cellulaires pour en fabriquer de nouveaux sans se soucier de passer par une règle locale de transition, il est encore nécessaire de définir les automates cellulaires de départ. Nous proposons ici une nouvelle caractérisation par clôture des automates cellulaires qui permet de s’affranchir complètement de la description locale. Nous en déduisons naturellement une caractérisation des automates cellulaires réversibles qui donne une présentation originale des automates cellulaires réversibles et simplifie leur construction.
Cas général
Nous montrons que tout automate cellulaire d’ensemble d’états de type J1, nK peut être obtenu par clôture d’une famille d’automates cellulaires aux comportements simples par les opérations de composition, produit cartésien et sous-automate.
Automate cellulaire autarcique. Un automate cellulaire autarcique A est un automate cellulaire de voisinage {0}. Chaque cellule évolue indépendamment des autres en utilisant une même règle locale de transition ψ : QA → QA. On note ψ la règle globale de transition de cet automate cellulaire. Un tel automate cellulaire est ultimement périodique.
Translation élémentaire. Une translation élémentaire σv de dimension d est une translation d’un vecteur de base de Zd ou de son opposé (i.e. v 1 = 1). L’ensemble des translations élémentaires de dimension d engendre toutes les translations de dimension d par composition.
Composition. La composition A ◦ B de deux automates cellulaires A et B de même ensemble d’états est l’automate cellulaire dont la règle globale de transition est la composition de leurs règles globales de transition (i.e. GA◦B = GA ◦ GB). La composition de deux automates n’est définie que si ceux-ci ont même ensemble d’états.
Produit cartésien. Le produit cartésien A × B de deux automates cellulaires A et B est l’automate cellulaire dont la règle globale de transition est le produit cartésien de leurs règles globales de transition. Nous allons travailler uniquement avec des alphabets de type J1, nK, aussi nous utiliserons implicitement une fonction de codage de J1, mK × J1, nK dans J1, mnK que nous noterons γ. Formellement, notre produit cartésien est défini par −1. Pour simplifier les notations, nous notons A × B × C le produit A×(B × C) et nous étendons γ à tout produit cartésien d’un nombre fini d’ensembles i=1J1, niK dans J1, i=1 niK.
Sous-automate. Le sous-automate à k états ⌊A⌋k d’un automate cellulaire A de dimension d et d’ensemble d’états J1, nK est l’automate cellulaire dont la règle globale de transition est la restriction de GA à l’ensemble J1, kKZd (i.e. G⌊A⌋k = GA). À une permutation des états près, tout sous-automate de A peut être obtenu ainsi. Le sous-automate n’est défini que lorsque la restriction à J1, kK de la règle de transition est bien à image dans J1, kK.
Théorème 9. Soit n un entier. Une application de J1, nKZd dans lui-même est la règle globale de transition d’un automate cellulaire si et seulement si elle appartient à la clôture des règles globales de transition des automates cellulaires autarciques et des translations élémentaires par les opérations de composition, produit cartésien et sous-automate.
Démonstration. Les automates cellulaires autarciques et les translations élémentaires sont des automates cellulaires. De plus, les opérations de composition, produit cartésien et sous-automate appliquées à des automates cellulaires produisent des automates cellulaires. Aussi, tout élément de la clôture est bien un automate cellulaire.
Réciproquement, soit A un automate cellulaire de dimension d, d’ensemble d’états J1, nK et de voisinage {v1, . . . , vν }. Considérons l’automate cellulaire partitionné Ap = Zd, J1, nKν , {v1, . . . , vν } , cν ◦ δA où cν est l’application de J1, nK dans J1, nKν définie pour tout état x par cν (x) = (x, . . . , x). Par construction A est un sous-automate de Ap où cν est l’application injective de QA dans QAp qui convient (i.e. cν ◦ GA = GAp ◦ cν ). Soit π une extension de γ ◦ cν en une application bijective de J1, nν K dans lui-même (i.e. vérifiant pour tout x ∈ J1, nK l’égalité π(x) = γ(cν (x))). Soit G la règle globale de transition définie par G = γ ◦ GAp ◦ γ−1. On peut alors exprimer GA de la manière suivante GA = π−1◦G◦π .
Il suffit donc de montrer que G est exprimable dans la clôture. Comme Ap est un automate partitionné, sa règle globale de transition peut être décomposée en une étape d’envoi de messages suivie de l’application autarcique de la fonction de transition, ici cν ◦δA. L’étape d’envoi des messages est un produit de translations. On sait que les translations sont toutes exprimables dans la clôture. Posons ψ = γ ◦ cν ◦ δA ◦ γ−1. On peut alors exprimer la règle globale de transition de A de la façon suivante G = π−1◦ψ◦(σ ו••×σ ) ◦ .
Ce qui conclut la démonstration.
Cas des automates cellulaires réversibles
Une manière naïve d’énumérer les automates cellulaires réversibles consiste à énumérer toutes les paires d’automates cellulaires et à tester pour chaque paire (A, B) si la composition A ◦ B est l’automate cellulaire identité (i.e. l’automate cellulaire I vérifiant pour toute configuration C l’égalité GI (C) = C), auquel cas l’automate cellulaire A est réversible et B est un inverse possible pour A. Certes cette méthode est intrinsèquement inefficace, mais le résultat d’indécidabilité de J. Kari [39] assure qu’il n’existe aucune méthode efficace. Cependant, nous proposons ici une nouvelle caractérisation des automates cellulaires réversibles qui nous semble plus satisfaisante pour la compréhension de la réversibilité.
Considérons la caractérisation du paragraphe précédent. Les trois opérations de composition, produit cartésien et sous-automate appliquées à des automates cellulaires réversibles produisent des automates cellulaires réversibles.
◮ En effet, pour les opérations de composition et de produit cartésien, c’est une conséquence évidente du théorème de G. Hedlund [19]. Pour l’opération de sous-automate, c’est une conséquence du corollaire 1. En effet, comme un automate cellulaire réversible est injectif, son sous-automate est nécessairement injectif et donc lui aussi réversible.
De ces considérations, on déduit qu’en conservant uniquement les translations élémentaires et les automates cellulaires autarciques réversibles comme objets de base, la clôture engendre un sous-ensemble des automates cellulaires réversibles. Nous montrons qu’en fait ils sont tous engendrés.
Théorème 10. Soit n un entier. Une application de J1, nKZd dans lui-même est la règle globale de transition d’un automate cellulaire réversible si et seulement si elle appartient à la clôture des règles globales de transition des automates cellulaires autarciques réversibles et des translations élémentaires par les opérations de composition, produit cartésien et sous-automate.

Table des matières

Introduction 
1 Automates cellulaires 
1.1 Automates cellulaires
1.1.1 L’objet et sa définition
1.1.2 Discussion et propriétés
1.1.3 Une caractérisation par clôture
1.2 Classifications
1.2.1 Genèse
1.2.2 Classification, calculabilité et complexité
2 Groupages 
2.1 Vers une extension du groupage
2.1.1 Algorithmique
2.1.2 Automates cellulaires unidirectionnels
2.1.3 Automates cellulaires nilpotents
2.1.4 Universalité intrinsèque
2.1.5 Synthèse
2.2 Interlude formel
2.2.1 Axiomatisation
2.2.2 Préordre
2.2.3 Universalités
2.3 Première esquisse du groupage
2.3.1 Transformations géométriques
2.3.2 Axiomatisation
2.4 Une extension du groupage carré
2.4.1 Définitions
2.4.2 Espace des phases
2.4.3 Exploration
2.4.4 Familles classiques d’automates cellulaires
2.4.5 Structure
2.5 Un groupage fortement structuré
2.5.1 Transformations géométriques généralisées
2.5.2 Axiomatisation
2.5.3 Exploration
3 Universalités 
3.1 Différentes notions d’universalité
3.1.1 Universalités
3.1.2 Un résultat étonnant
3.1.3 Prototypes ayant de bonnes propriétés
3.1.4 Minimisation
3.2 Indécidabilité de l’universalité intrinsèque
3.2.1 Un automate cellulaire intrinsèquement universel
3.2.2 Automates cellulaires chaudières
3.2.3 Résultat
3.3 Un automate universel bilinéaire à deux états
3.4 Un automate universel à 6 états
3.4.1 Un automate cellulaire universel simple à 8 états
3.4.2 Affinement du nombre d’états requis
4 Pour aller plus loin 
A Groupage carré
A.1 Définitions
A.2 Propriétés élémentaires
A.3 Le bas de l’ordre
A.3.1 Automates cellulaires dynamiquement simples
A.3.2 Automates cellulaires algébriquement simples
A.4 Chaînes infinies bornées
A.5 Chaînes infinies non-bornées

Télécharger le rapport complet