Projet de deuxième année : plate-forme d’étude des automates cellulaires

 

 

Table des matières

 

 

Rapport d’avancement 2

Introduction. 2

Modélisation et expérience. 2

Informatique. 3

Premiers modules « mathématiques ». 3

Nomenclature des termes rapportés aux automates cellulaires. 4

1.     Définitions structurelles. 4

2.     Définitions dynamiques. 4

3.     Propriétés des structures. 5

4.     Propriétés des trajectoires. 5

Réflexions sur un testeur d’inversibilité. 6

Nouvelles notions théoriques. 7

I. Potentiel et classes d’équivalence. 7

I.1 Potentiels de lignes. 7

I.2 Classe d’équivalence et potentiel de classe. 9

I.3 Potentiel et automates : pertes de potentiel 9

II. Utilisation de ces notions. 12

II.1 Une nouvelle grandeur caractérisant les ACL. 12

II.2 Utilisation en programmation. 12

II.3 Nouvelle vision des règles, proportion d’inversibles. 13

III. Conclusion. 17

Rapport d’avancement

 

Introduction

 

            Notre première phase de travail pour le projet de deuxième année a été marquée par des prises de décision concernant le domaine dans lequel nous souhaitions effectuer la modélisation ainsi que sur la structure de la plate-forme. Nous avons également poursuivi notre réflexion à propos d’aspects mathématiques des automates cellulaire, réflexion préalable à la réalisation des modules d’étude théorique. Ce dossier est composé principalement de deux documents retraçant nos avancées dans deux directions d’études mathématiques.

 

Modélisation et expérience

 

            Nous souhaiterions effectuer la modélisation prévue dans le cadre de la thermique. Nous serions intéressés par exemple par modéliser l’évolution de la température dans un objet métallique (avec des conditions initiales et aux limites à définir). Ce type de modélisation offre en effet l’avantage de mettre en jeu une variable scalaire (la température), plus simple à maîtriser qu’une variable vectorielle. Ce choix nous paraît raisonnable pour une première modélisation. De plus, on peut imaginer commencer par modéliser un objet approximable à une dimension (type barre), puis à deux et enfin à trois en fonction de la pertinence des résultats que nous obtenons.

            Pour la modélisation proprement dite, nous distinguons deux types d’utilisation des automates :

 

·        Une modélisation où le « temps » des automates cellulaires correspond à une discrétisation du temps réel. C’est à dire que la donnée de la première ligne reviendrait à la donnée de la condition initiale, et le calcul d’un état à partir du précédent au passage de t à t + Dt. Chaque cellule contient une information reliée directement au phénomène étudié (ici, la température).

 

·        Une modélisation où le temps réel discrétisé est une dimension de l’état de l’automate. Chaque état contient des dimensions spatiales, temporelles, et des dimensions en liaison avec l’inconnue. Le passage d’un état au suivant correspond à un affinement. Les cellules pourraient alors ne contenir qu’une affirmation binaire, 1 si la combinaison espace, temps, valeur de la variable peut avoir un sens, 0 si elle n’en a pas.

 

Les règles d’évolution des automates cellulaires sont très différentes dans les deux cas. La première méthode paraît plus facile à mettre en œuvre, mais nous aimerions réfléchir également à la seconde.

Nous imaginons deux types de démarches de travail :

 

·        Déduire de la discrétisation des lois physiques une modélisation par automates cellulaires que l’on valide ensuite par l’expérience

 

·        Rechercher des automates cellulaires correspondant aux résultats de l’expérience et les confronter aux lois physiques.

 

Nous n’excluons pas d’effectuer les deux démarches (dans l’ordre donné).

 

Informatique

 

            Nous sommes arrivés à la conclusion qu’il n’était pas utile de réunir dans une même plate-forme les modules de type « mathématiques » (en vue d’étude théoriques) et les modules de type « physiques » (outils de modélisation).

            Nous ne comptons en effet étudier sous un aspect mathématique que des automates cellulaires binaires de dimension 1 avec conditions limites périodiques. Les automates cellulaires utiles pour la modélisation seront de dimension supérieure à 1, avec des cellules prenant leurs valeurs dans des espaces éventuellement différents de {0,1}, et surtout ils n’auront pas a priori des conditions aux limites périodiques, mais fixées.

            Le fait de réaliser ces deux plates-formes en parallèle nous paraît cependant pertinent. Cela permet d’avoir un aperçut cohérent de l’objet, et d’effectuer certains tests en dimension inférieure avant de commencer la modélisation.

            Cette séparation permettra de mieux se concentrer sur les objectifs dans chacun des domaines. Pour l’étude « physique », il faut un programme qui permette d’entrer facilement des conditions initiales et des règles d’évolution complexes, problème qui se pose très différemment pour les automates de dimension 1.

 

Premiers modules « mathématiques »

 

            Nous joignons à ce rapport une fiche de nomenclature, expliquant certaines notions que nous utilisons en rapport avec les automates cellulaires, ainsi qu’une page d’explication sur le principe d’un détecteur d’automates inversibles.

            Suivent deux documents de recherche théorique portant les bases de certains modules d’étude. Le premier concerne les notions de potentiel de ligne et de classe d’équivalence, le second les probabilités d’apparition de voisinage pour des lignes de « grandes largeur ».

Nomenclature des termes rapportés aux automates cellulaires

 

1.    Définitions structurelles

• Cellule : objet portant des valeurs prises dans un ensemble discret
• Réalisation d’une cellule : cellule affectée d’une valeur

• Espace cellulaire : organisation de cellules, munie d’une relation de positionnement de chaque cellule par rapport aux autres, qui est indépendante de la cellule considérée
• Etat : réalisation d’un espace cellulaire

 

• Espace cellulaire dimensionné : espace cellulaire dont on peut repérer chaque cellule par rapport à une autre par un vecteur de
• Dimension : dimension de (cf. Espace cellulaire dimensionné)
• Ligne : état d’un espace cellulaire de dimension 1, dont les cellules sont à valeur dans {0,1}

 

• Taille : paramètres topologiques d’un espace cellulaire
• Largeur : taille d’une ligne

 

• Voisinage : distribution de cellule relativement à une autre
• Environnement : réalisation d’un voisinage
• Bit : cardinal d’un voisinage

2.    Définitions dynamiques

• Règle : application de l’ensemble des environnements dans l’ensemble de réalisation des cellules
• Automate cellulaire libre (ACL) : couple formé par une règle et une taille
• Automate cellulaire appliqué (ACA) : suite des états résultant de la réitération de l’application d’un ACL à un état initial
• Génération d’un état d’un ACA : nombre d’itération de l’ACL associé depuis l’état initial.

3.    Propriétés des structures

• Motif : partie d’un état
• Période d’un état E : taille d’un motif suffisant à la reconstitution de E

 

• Potentiel d’un état E : plus petite période de E
• Motif minimal d’un état E : motif reconstituant E, de taille son potentiel
• Classe d’équivalence : ensemble d’états ayant même potentiel minimal

 

• Vecteur probabilité d’un couple (voisinage V, état E) : probabilités d’apparitions des environnements de V dans E
• Vecteur probabilité réduit d’un couple (voisinage V, état E) : probabilités d’apparitions d’environnements de V dans E suffisantes pour définir le vecteur probabilité de (V,E)
• Fonction de probabilité associée à un ACL A : application qui au vecteur probabilité de (V, E) associe celui de (V, A(E))

4.    Propriétés des trajectoires

• Cycle d’un ACA A: ACA de même ACL que A, dont l’état initial est contenu dans A, et se retrouve après un certain nombre de générations.
• Période d’un cycle C : plus petit nombre de générations nécessaire à la réapparition de l’état initial de C (noté T)
• Régime transitoire d’un cycle C d’un ACA A : nombre de génération de A entre l’état initial de C et celui de A (noté t)

 

 

Réflexions sur un testeur d’inversibilité

 

            Le premier programme que nous avons réalisé en C++ permettait déjà de tester si un automate était inversible ou non. Ce n’était cependant pas l’objectif premier de ce programme. Ce dernier donne, en particulier, une moyenne avec pondération de la longueur des cycles d’un ACL ainsi qu’une moyenne également pondérée du chemin avant d’arriver à un cycle. Lorsque cette dernière moyenne est nulle, toutes les lignes sont sur un cycle, et donc l’automate est inversible.

            Il ne s’agit bien sûr pas de la méthode la plus directe pour savoir si un ACL est inversible. Nous avons développé, cette année, un programme dont l’unique fonction est de tester l’inversibilité.

 

            Son fonctionnement repose sur le remplissage d’un tableau T ayant pour taille le nombre de lignes possibles pour la largeur L de l’ACL que l’on souhaite tester. Ce tableau indique si une ligne est l’image d’une autre.

            Par exemple, on aura T(3) = 0 si aucune ligne ne pointe par l’ACL étudié vers la ligne (0, 0, …, 0, 1, 1) dont la transcription décimale vaut 3. Plus généralement, si T(3) = k, il existe k lignes dont l’image est la ligne (0, 0, …, 0, 1, 1).

            Le tableau se remplit en effectuant une boucle sur l’ensemble des ligne. Pour chaque ligne, on calcule l’image et on ajoute 1 dans la colonne du tableau correspondant à la ligne image. Une fois la boucle finie, le tableau peut avoir deux types d’aspects : soit il contient un 1 dans chaque colonne, auquel cas l’ACL est inversible (on peut le voir de deux manières : il y a injectivité donc bijectivité car aucun nombre du tableau n’est supérieur à 1 ; il y a surjectivité donc bijectivité car aucun nombre du tableau n’est nul), soit la configuration est autre, avec au moins un 0 et un nombre supérieur à 1, auquel cas l’ACL n’est pas inversible.

 

            En fait, le testeur que nous avons réalisé repose sur l’injectivité. Il arrête la boucle dès qu’une ligne pointe vers une ligne déjà atteinte précédemment, c’est à dire dont la colonne correspondant dans le tableau contient déjà un 1. Le programme effectue ainsi un nombre de calculs d’images compris entre 2 (si les lignes (0, …, 0) et (0, …, 0, 1) ont la même image)et 2^L (si l’automates est inversible).

 

            Affin d’accroître la rapidité des calculs, le programme vérifie si l’énoncé de la règle contient autant de 1 que de 0 lorsque L ³ 2r + 1 (où r est le rayon de la règle), avant de créer le tableau T (cf « Nouvelles notions théoriques » II. 3 ). De plus, nous utilisons la méthode des potentiels croissants décrite dans ce même document.

 

            Le testeur d’inversible de la plate forme s’inspirera largement de ce programme. Le tableau dont nous expliquons plus haut la signification et le calcul peuvent également être utilisés dans d’autres fonctions de la plate forme. En particulier, il peut servir à détecter les Jardins d’Eden d’un ACL, c’est à dire les lignes n’ayant aucun antécédent (valeur nulle dans le tableau). La Connaissance des Jardins d’Eden paraît nécessaire à la réalisation de cartes d’ACL (il s‘agit des points de départ des trajectoires).

 

 

Nouvelles notions théoriques

 

I. Potentiel et classes d’équivalence

 

Depuis notre travail de première année sur la complexité des automates cellulaires, nous avons été amenés à construire de nouvelles notions relatives aux automates cellulaires. Il ne s’agit pas d’idées révolutionnaires. Elles ont été de toute évidence utilisées précédemment, mais nous n’avons pas trouvé de publications en faisant état. Nous avons donc choisi notre propre nomenclature, adaptée à l’étude théorique que nous souhaitions faire sur les automates cellulaires. Il s’agit avant tout de la notion de potentiel de ligne.

Nous nous intéressons ici exclusivement aux automates binaires de dimension 1, de largeur finie avec conditions aux bords circulaires. Beaucoup de résultats seraient généralisable à des dimensions supérieures et à Z/kZ, k>2.

 

I.1 Potentiels de lignes

 

            En faisant tourner des automates cellulaires sur le programme que nous avions réalisé, il nous est apparu que des lignes de configuration quelconques donnaient parfois après quelques applications de l’automate des lignes avec des périodicités, comme par exemple :

 

0

1

1

0

1

1

0

1

1

 

de période 3, ou

 

0

1

0

1

0

1

0

1

 

de période 2, mais aussi de période 4. Remarquons également que, puisque ce que nous appelons ligne est en fait un cercle, avec raccord des deux extrémités entre elles, la première ligne est également de période 6, voire 9, la largeur. Toute ligne est au moins de période sa largeur (le périmètre du cercle).

 

            Nous avons ainsi défini le potentiel d’une ligne comme étant sa plus petite période (la première ligne est de potentiel 3, la seconde de potentiel 2), résolvant ainsi le problème d’unicité. On peut déjà donner quelques propriétés du potentiel. Puisque toute ligne est de période L (sa largeur), le potentiel d’une ligne est inférieur ou égal à la largeur. De plus, le potentiel ne peut prendre comme valeur que les diviseurs de L. Le potentiel peut être vu comme une fonction de l’ensemble des lignes vers l’ensemble des diviseurs de la largeur. On voit l’importance que peuvent prendre les propriétés arithmétiques de L.

 

            Regardons maintenant l’ensemble des lignes possibles pour une largeur L donnée (il y en a 2^L). Il y a toujours 2 lignes de potentiels 1 : ce sont les lignes formées uniquement de 1 et uniquement de 0. Le potentiel suivant (le plus petit strictement supérieur à 1) dépend de L. Si L est premier par exemple, la valeur suivante du potentiel sera L lui même.

 

            Imaginons que L soit pair. 2 est alors le potentiel suivant. Il y a quatre lignes de période 2 possibles :

 

0

0

0

0

0

0

0

…

 

0

1

0

1

0

1

0

…

 

1

0

1

0

1

0

1

…

 

1

1

1

1

1

1

1

…

 

            On remarque donc que parmi ces quatre lignes, deux ne sont pas de potentiel 2, mais 1. Si l’on veut calculer le nombre de génération de potentiel V, il faut soustraire au nombre de lignes de période V (2^v ) les lignes qui sont de période inférieure divisant V.

            On obtient ainsi la formule :

 

            où N_v représente le nombre de lignes de potentiel V

            W_v est l’ensemble des diviseurs de V à l’exclusion de ce dernier

 

            On a ainsi une formule de récurrence permettant de trouver N_v à partir du nombre de lignes de potentiels les diviseurs de V. Remarquons que cette formule ne fait pas intervenir la largeur L (celle-ci intervient pour le choix de V parmi les diviseurs de L). On peut donc donner une table des valeurs obtenues à partir de la formule de récurrence.

 

V	Nv
1	2
2	2
3	6
4	12
5	30
6	54
7	126
8	240
9	504
10	990
11	2046
12	4020
13	8190

 

            Pour une largeur L=12 par exemple, on peut déduire la répartition des lignes par potentiel :                

            V=1 :   2 lignes

            V=2 :   2 lignes

            V=3 :   6 lignes

            V=4 :   12 lignes

            V=6 :   54 lignes

            V=12 : 4020 lignes

La répartition est très différente pour une largeur première. Prenons L=11

 

            V=1 :   2 lignes

            V=11 : 2046 lignes

I.2 Classe d’équivalence et potentiel de classe

 

On peut également remarquer que V divise toujours N_v. Cette propriété se comprend mieux avec l’introduction de la notion de classe d’équivalence. Une classe d’équivalence est un ensemble de lignes stable par « rotation ». Par exemple,

 

0

0

1

 

0

1

0

 

1

0

0

 

sont les trois lignes de la classe d’équivalence [001] (notée aussi [010] ou [100] ). Il est évident que toutes les lignes d’une classe d’équivalence ont même potentiel – nommé potentiel de classe – et que le nombre d’éléments d’une classe d’équivalence est égal à ce potentiel.

A partir de là, on déduit que les lignes d’un potentiel se regroupent en classe d’équivalence de cardinal le potentiel en question, et donc que ce dernier divise le nombre de ligne caractérisées par ce potentiel.

Il serait possible de définir le potentiel de classe comme le cardinal de cette classe, et le potentiel d’une ligne comme le cardinal de la classe d’équivalence à laquelle elle appartient.

 

En résumé, l’ensemble des lignes correspondant à une largeur se regroupent en potentiels, et à l’intérieur de ces potentiels en classes d’équivalence.

 

I.3 Potentiel et automates : pertes de potentiel

 

            Nous avons choisi d’appeler la période minimale d’une ligne son potentiel par une analogie physique. Lorsque l’on considère un enchaînement de ligne généré par un automate cellulaire, il peut s’opérer une perte de potentiel : on passe d’une ligne (ou génération) de potentiel V à une ligne de potentiel V’, V’ divisant V.

            Exemple de perte de potentiel : (règle 150, largeur 6)

 

1	0	0	0	0	0	a
1	1	0	0	0	1	b
1	0	1	0	1	0	c
1	0	1	0	1	0	d
1	0	1	0	1	0	e

 

            Le passage de la ligne b à la ligne c correspond au passage d’un potentiel 6=L à un potentiel 2

 

            Par contre, une augmentation de potentiel n’est pas possible. La périodicité des environnements de la génération antécédent impliquera toujours la périodicité de la génération image. Une perte de potentiel est donc un phénomène irréversible. Un automate permettant des chutes de potentiel est nécessairement non inversible. En effet la génération située après la perte possède au moins V / V’ antécédents. Si on reprend l’exemple précédent, les lignes

 

1

1

0

0

0

1

(b)

 

0

1

1

1

0

0

 

0

0

0

1

1

1

 

donnent toutes les trois la ligne (c).

 

            Un automate peut toutefois être non inversible sans présenter de perte de potentiel. La perte de potentiel correspond seulement à un certain type de non inversibilité d’automates cellulaires (la non inversibilité étant le cas le plus courant parmi les automates cellulaires).

           

            Notre travail précédent était fortement focalisé autour des cycles d’automates cellulaires (cycles « temporels »). Puisqu’il y a un nombre fini de lignes possibles, un automate finira par repasser par une ligne déjà générée précédemment. On appelle cycle la séquence de lignes bouclée sur elle même. On déduit de l’impossibilité de remonter les potentiels que toutes les lignes d’un cycle ont même potentiel.

 

            La notion de potentiel permet de structurer l’espace des lignes indépendamment des automates (en fonction de la largeur mais indépendamment de toute règle d’évolution). Regroupons les lignes par classes d’équivalence, et ces classes d’équivalence par potentiel. Les parois entre zones de potentiel sont perméables seulement si l’un divise l’autre et uniquement dans le sens des potentiels décroissants. Par exemple, il existe des chemins de toutes les zones de potentiel différent de 1 vers la zone de potentiel 1. Mais cette dernière ne possède aucun chemin vers l’extérieur (c’est à dire qu’il n’existe aucune transition potentielle par un automate cellulaire vers des lignes de potentiel autre que 1). De plus, si par exemple 6 divise la largeur, la paroi entre les zones de potentiel 3 et 2 est totalement imperméable dans les deux sens (mais ces zones peuvent mener toutes deux à la zone 1 et être atteintes depuis la zone 6).

            A cette « structure » indépendante de la règle type schéma d’équipotentielles viennent se greffer, pour une règle donnée, les trajectoires de l’automate cellulaire (pour toutes les configurations initiales possibles. Cf notion d’ACL). Ces trajectoires sont caractérisées par des cycles situés entièrement dans une zone de potentiel.

 

Exemple fantaisiste pour L=6   Les points noirs représentent le lieu de perte de potentiel. V/V’ chemins identiques convergent alors vers la génération antécédent. Les cycles sont chacun contenus entièrement par une zone de potentiel. Le frontière potentiel 2, potentiel 3 est infranchissable. Cette représentation ne tient pas compte des parallélismes induits par les classes d’équivalence.

 

 

 

Pour finir, observons l’allure des automates inversibles. L’injectivité implique qu’ils ne soient formés que de cycles. Tous les potentiels sont donc « indépendants ».

 

Exemple d’automate inversible pour L=6   Les trajectoires forment des cycles, aucune paroi de zone de potentiel n’est franchie.

 

 

II. Utilisation de ces notions

 

II.1 Une nouvelle grandeur caractérisant les ACL

 

            Il paraît intéressant de connaître pour un automate, sa propension à descendre en potentiel. Il s’agit en effet d’un indicateur d’une certaine forme d’inversibilité. Par exemple, les automates qui s’ « effondrent » sur la ligne 0 ou sur la ligne 1 seraient caractérisés par une forte propension à perdre du potentiel.

            Ce test pourrait être ajouté au panel étude mathématique des automates cellulaires de la plate-forme. Différents critères pourraient être retenus, comme le nombre de franchissement des zones de potentiel. Il suffit de faire une boucle sur l’ensemble des lignes et de tester si la ligne image a même potentiel ou non que la ligne antécédent, et d’incrémenter un compteur à chaque perte de potentiel. Ce critère ne semble pas tenir compte de l’importance de la chute (rapport des potentiels avant et après perte). Cependant, on a vu que la perte de potentiel correspondait à la convergence sur la ligne image d’un nombre de lignes antécédents (appartenant à une même classe d’équivalence) égal au rapport précédemment cité.

            Le nombre de pertes de potentiel (normé au besoin par le nombre de lignes pour rendre possible une comparaison entre ACL de largeur différente) est un nombre compris entre 0 et 2^L -2 (les deux lignes de potentiel 1 ne peuvent conduire à une perte de potentiel). Les automates inversibles ont une propension nulle, mais cette dernière n’est pas caractéristique de l’inversibilité.

            La réalisation de ce nouveau module nécessite la création d’une fonction donnant le potentiel d’une ligne.

 

II.2 Utilisation en programmation

 

            La notion de potentiel a déjà été utilisée en programmation pour accélérer la détermination d’inversibles. Au lieu de tester directement l’inversibilité d’un ACL de règle r et de largeur L, on peut regarder l’ACL de règle r et de largeur V, V étant un diviseur de L (donc un potentiel). Si l’ACL (r,V) n’est pas inversible, alors (r,L) ne l’est pas non plus. Lorsque l’on étudie l’inversibilité sur de grosses largeurs (supérieures à 10 par exemple), il est souvent plus rapide d’étudier l’inversibilité par potentiels croissants (d’abord pour L=1, ce qui revient à vérifier que la ligne 0 et la ligne 1 ont des images différentes, puis pour le plus petit potentiel supérieur à 1, etc), l’opération étant arrêtée lorsque l’on a trouvé un ACL non inversible. La détermination de l’inversibilité par cette méthode est plus longue que par la méthode directe lorsque l’automate est effectivement inversible, puisqu’au lieu d’effectuer le test seulement sur (r,L), on l’effectue sur (r,1), (r,V), (r,V’), …, (r,L). Mais lorsque l’on effectue un balayage sur les règles affin de trouver les inversibles, nous avons noté un gain de temps, imputable à la « faible » proportion d’inversibles parmi les automates.

II.3 Nouvelle vision des règles, proportion d’inversibles

 

            Grâce à la notion de potentiel, on peut aussi dégager une nouvelle vision des règles. Pour une largeur L fixée, on considère ici les règles de bit L, c’est à dire les règles dont l’environnement est étendu à l’ensemble des L cellules, et non plus seulement aux cellules proches (notion de rayon). Cet élargissement est motivé par la constatation que les inverses des automates de rayon donné ne sont pas a priori des automates de même rayon, mais des automates de bit L. Notons aussi que ce passage a peu de sens pour l’application des automates cellulaires à la modélisation de phénomènes physiques : le caractère local de l’environnement déterminant l’état d’une cellule est dans ce cas fondamental, ne serait-ce que pour la faisabilité des calculs.

            On peut représenter ainsi la donnée d’une règle de bit L : pour tout environnement de taille L, on donne l’image obtenue dans la cellule considérée :

 

1	0	0	1	1	0	0
1

 

            Notons que le fait d’écrire la cellule étudiée de la ligne image à gauche est une convention totalement arbitraire. Par exemple, la forme

 

0	1	0	0	1	1	0
	1

 

est strictement équivalente. Il n’y a plus de raison, comme pour les règles avec rayon, de « centrer » la cellule considérée.

            Pour la largeur L, il y a 2^L environnements possibles, et donc règles définissables (puisque chaque environnement peut donner 0 ou 1).

            Construisons maintenant ces mêmes règles en utilisant la notion de classe d’équivalence. Considérons les éléments de la règle (L=4 dans l’exemple) :

 

1	1	0	0		1	1	0	0		1	1	0	0		1	1	0	0
1						0						0						0

 

Il serait possible de les regrouper en écrivant :

 

1	1	0	0
1	0	0	0

 

c’est à dire l’image de la ligne (1,1,0,0), et plus généralement, par rotation, l’image de la classe d’équivalence [1,1,0,0]. Pour une ligne de potentiel 2, la donnée de seulement 2 éléments de règle suffit pour trouver l’image de la classe.

 

1	0	1	0	et	1	0	1	0	permettent de déduire
0						1

 

 

1	0	1	0
0	1	0	1

            De même,

 

0	0	0	0
1

 

suffit pour obtenir :

 

0	0	0	0
1	1	1	1

 

            On peut donc donner une règle en donnant l’image de chaque classe d’équivalence, c’est à dire en donnant pour chaque classe d’équivalence l’image d’un de ces éléments (disons celui dont le nom décimal est le plus petit affin d’assurer l’unicité). L’image n’est pas quelconque. La périodicité de la ligne antécédent doit réapparaître dans la ligne image. Une classe d’équivalence peut pointer vers n’importe quelle ligne de période V, le potentiel de la classe, et de telles lignes sont au nombre de 2^V.

            Si on regarde maintenant le nombre de possibilités pour un potentiel V, on trouve

, C_V où est le nombre de classe d’équivalence du potentiel V, égal comme on l’a vu plus tôt, à N_V/ V.

            Pour obtenir le nombre total de règles possibles, on fait le produit par potentiels. On obtient

, E_L étant l’ensemble des diviseurs de L (L compris).

 

On a ainsi vérifié que l’on obtenait le même nombre de règles par cette vision. Celle-ci est particulièrement intéressante puisqu’elle permet de dénombrer le nombre d’ACL inversibles pour une largeur L donnée.

 

En effet, il suffit de regarder, potentiel par potentiel, le nombre de manières de former des cycles avec les N_V lignes de la zone. Autrement dit, on peut lier les lignes entre elles sans autres conditions que de garantir l’injectivité.

Prenons une première classe d’équivalence. Son plus « petit élément » peut pointer vers une des C_V classes du potentiel, et à l’intérieur de la classe choisie vers un des V éléments. Il y a ainsi V.C_V possibilités.

La seconde classe d’équivalence que l’on considère ne peut plus pointer que vers
C_V-1classes non encore atteintes. Et ainsi de suite. On obtient finalement possibilités pour le potentiel V, soit en tout :

 ACL inversibles pour la largeur L

 

Si on s’intéresse maintenant à la proportion d’inversibles pour une largeur :

 

On remarque que la proportion d’automates cellulaires s’écrit comme le produit de quantités I_v indépendantes de la largeur, que l’on pourrait nommer proportion d’inversibles au potentiel V . On pourrait former des tables, comme pour N_v et C_v de ces quantités. Nous envisageons la création d’un programme annexe à la plate-forme permettant de déterminer ces tables. I_v serait donné sous forme d’une fraction irréductible. On peut donner ici les 6 premières lignes de la table générale – avec I_v approximé :

 

V	Nv	Cv	Iv
1	2	2	0,5
2	2	1	0,5
3	6	2	0,281
4	12	3	0,0937
5	30	6	0,0419
6	54	9	0,000203

 

            On en déduit :

 

L	cL
1	0,5
2	0,25
3	0,141
4	0,0234
5	0,0210
6	0,000014

 

            Nous n’envisageons d’étudier que des règles avec rayon, la seule opération d’entrée d’une règle de bit L pour une largeur 6 demandant de définir 64 paramètres. Le nombre d’inversibles de bit L donne cependant une information sur le nombre d’inversibles de rayon donné, ne serait-ce qu’une majoration.

 

            De plus, le fait de se placer dans le cadre plus général des règles de bit L rend certaines propriétés, intuitées pour des règles à rayon, évidentes à démontrer.

Nous avons en particulier très vite remarqué qu’une règle de rayon r dont l‘énoncé ne présentait pas autant de 0 que de 1 ne pouvait engendrer des ACL inversibles lorsque
L ³ (2r + 1). Par exemple, la règle 222 (rayon 1) qui s’écrit :

 

 

présente six 1 et deux 0 et n’est inversible pour aucune largeur supérieure ou égale à 3. (Pour L=1 et L=2, 222 est inversible : c’est l’identité. Seuls le premier et le dernier élément de la règle sont utiles pour L=1, et pour L=2, les éléments (1), (3), (6), (8) ).

            La démonstration n’est cependant pas évidente, à moins de passer en règle de bit L. On considère un ACL inversible. Sa règle de rayon r donné est ainsi traduite en bit L, c’est à dire qu’on la complique a priori inutilement. Mais on a alors une correspondance entre la règle et la « carte » de l’ACL. En particulier, on retrouve la règle en regardant, pour chaque classe d’équivalence, l’image de l’un de ses éléments. On peut aussi regarder l’antécédent de toute ligne et se défaire des informations redondantes (une seule ligne par classe d’équivalence aurait suffit) en ne retenant que l’information relative à la première cellule de la ligne image.

 

 

Par exemple, de	0	1	0	0	on ne retiendra que	0	1	0	0
	1	0	0	1		1

 

le reste de l’information étant donné par les images des autres lignes de la classe [0,1,0,0].

On obtient alors les  éléments de la règle, avec pour image des environnements la première cellule d’une ligne. Or puisque l’ACL est inversible, toute ligne est l’image d’une autre, et donc la première cellule de chacune des lignes apparaîtra en tant qu’image d’environnement dans l’énoncé de la règle. Parmi ces 2^L lignes, la moitié commence par 0, l’autre par 1. Si l’ACL est inversible, il y a donc nécessairement autant de O que de 1 dans l’énoncé de la règle.

 

III. Conclusion

 

            Nous avons montré l’intérêt que pouvaient avoir les notions de potentiel et de classe d’équivalence, intérêt théorique aussi bien que pratique (programmation). Remarquons pour finir que l’on peut définir un automate cellulaire en utilisant uniquement la notion de classe d’équivalence.

            Traduisons le fait qu’une application @ de {0,1}^L dans {0,1}^L respecte le principe des classes d’équivalences, c’est à dire que les images des éléments d’une classe d’équivalence appartiennent à une même classe d’équivalence, et que si l et l’ sont deux éléments de la classe d’équivalence antécédent, on passe de @(l) à @(l’) par la même « rotation » que de l à l’.

            Pour cela, notons g l’application de {0,1}^L dans {0,1}^L qui au L-uplet (a₀, a₁,… a_L-1) associe le L-uplet (a₁, …a_L-1, a₀), c’est à dire l’automate appelé « shift gauche », le décalage de la ligne d’un cran à gauche.

            Le principe des classes d’équivalences s’écrit alors :

 

"kÎN, g^ko@ = @og^k ,

 

            ce qui est équivalent à go@ = @og (de manière évidente)

 

            Respecter le principe des classes d’équivalences équivaut donc pour une application à commuter avec l’application « shift gauche ». Le respect du principe des potentiels, c’est à dire que la période de la ligne image divise celle de la ligne antécédent, s’écrit :

 

            Si g^V(l) = l , alors g^Vo@(l) = @(l) où l est une ligne (l Î{0,1}^L)

 

            On démontre aisément que le respect du principe des classes d’équivalences implique celui des potentiels (g^Vo@(l) = @o g^V(l) = @(l) si @ commute avec g ).

 

            Montrons enfin que la définition d’ACL retenue dans la dernière partie du chapitre précédent est équivalente à : « @ : {0,1}^L ® {0,1}^L commute avec g », donc @ obéit au principe des classes d’équivalence.

            La définition d’ACL de largeur L avec règle de bit L a priori s’écrit :

 

@ : {0,1}^L ® {0,1}^L est un ACL de largeur L

si et seulement si il existe f : {0,1}^L ® {0,1} , telle que :

@(a₀, a₁, …, a_L-1) = ( f(a₀, a₁, …, a_L-1), f(a₁, a₂, …,a_L-1,a₀), …, f(a_L-1, a₀, …,a_L-2) )

 

(existence d’une règle locale appliquée pour chacune des cellules de la ligne image)

 

soit A l’ensemble des applications de {0,1}^L ® {0,1}^L satisfaisant la condition ci dessus, B l’ensemble des commutants de g.

 

¨ si @ ÎA,

" (a₀, a₁, …, a_L-1) Î{0,1}^L, (on regarde la k^ème composante)

@og(…,a_k,…) = @(…,a_k+1,…) = (…,f(a_k+1, a_k+2,…, a_k-1),…) = go@(…,a_k,…)

donc AÌB

 

¨ si @ÎB,

on peut écrire @ sous la forme

"  (a₀, a₁, …, a_L-1)Î{0,1}^L,

@(a₀, a₁, …, a_L-1) = (f₀(a₀, a₁, …, a_L-1), f₁(a₁, a₂, …, a₀), …, f_L-1(a_L-1, a₀, …, a_L-2) )

 

comme  @ et g commutent :

"       (a₀, a₁, …, a_L-1)Î{0,1}^L,

@og(a₀, a₁, …, a_L-1) = go@(a₀, a₁, …, a_L-1)

soit @(a₁, a₂, …, a₀) = g(f₀(a₀, a₁, …, a_L-1), f₁(a₁, a₂, …, a₀), …, f_L-1(a_L-1, a₀, …, a_L-2) )

et encore :

(f₀(a₁,…), f₁(a₂, …), …, f_L-1(a₀, …) ) = (f₁(a₁,…), f₂(a₂, …), …, f₀(a₀, …) )

d’où on déduit f₀ = f₁ = … = f_L-1

donc BÌA, et finalement A=B.

 

Nous avons obtenu une définition concise et simple des ACL de règle d’environnement quelconque. Nous pourrions également les définir comme les commutants du « shift droit », ou d’une composition k fois du « shift gauche » ou « droit » avec k et L premiers entre eux.