L’introduction des mesures de complexité l et p à la place des valeurs correspondantes t et T peut être considérée comme le passage d’un point de vue statistique à un point de vue cartographique. La carte d’un automate serait la représentation de tous les états possibles avec des liaisons orientées traduisant la relation génération mère - génération fille. Sur ce schéma, l correspond à la longueur cumulée des chemins menant aux cycles, p à la somme des périmètres de tous les cycles.

Cette vision offre de nouvelles perspectives. Elle permet d’appréhender un ACL dans toute sa complexité. Il semble que nous serons amener à définir de nouveaux types de mesure de complexité attachés à cette vision.

Notre première approche, plutôt d’ordre statistique, ainsi qu’avec des considérations temporelles, permet une programmation plus simple. Elle est adaptée à l’utilisation en informatique. La génération d’une carte d’un ACL est beaucoup plus complexe à mettre en œuvre. Nous avons déjà réfléchis à quelques grandes structures du programme générateur de carte, que nous espérons pouvoir réaliser prochainement.

Notre idée consiste à considérer un ACL comme les passages de Jardin d’Eden à des cycles. Et pour intégrer chacun des chemins remplissant cette fonction, il y a deux manières d’aborder le problème : partir des cycles ou des Jardin d’Eden.

Nous savons déjà comment connaître la taille et les générations d’un cycle auquel mène un ACA de règle, largeur et condition initiale données. La difficulté est que jusqu’alors, nous n’avons pas cherché à identifier les cycles. On regardait pour chaque génération initiale la durée du cycle et le temps mis pour y arriver, et on ne s’intéressait absolument pas au fait que deux génération initiales puisse mener au même cycle, d’autant moins au fait que les chemins partant de deux conditions initiales vers un cycle puisse se rejoindre avant l’arrivée au cycle. Il s’agit maintenant de données fondamentales, nécessaires à l’élaboration de la carte d’un ACL.

Afin d’identifier un cycle, il suffit de connaître une des génération de ce cycle puisque l’itération de la règle redonne l’intégralité des générations du cycle très rapidement. Un des premiers module du programme consisterait à détecter et répertorier les différents cycles de l’ACL. Pour cela, il faudrait lancer successivement les ACA correspondant à chacune des générations initiales comme nous l’avons fait jusqu’à présent et stocker en mémoire les cycles par lesquels l’automate passe.

La première génération donnerait un cycle qui serait entré en mémoire par l’intermédiaire d’une de ses génération (avec, par préoccupation pratique la taille de ce cycle pour information, puisque nos algorithmes de recherche de cycle permettent directement de connaître la taille). La deuxième génération amènerait également à un cycle qui sera lui aussi stocké sous la forme d’un de ses états, à la condition que le nouveau cycle détecté ne contienne pas la ligne caractéristique du premier cycle. Le cycle du n ème ACA serait stocké après avoir vérifié qu’il ne contient aucune des lignes précédemment enregistrées.

A. 2. Génération des chemins

On a ainsi obtenu un tableau donnant k cycles, avec une de leurs générations et la taille du cycle (nous parlions auparavant de durée du cycle ; le changement de perspective nous amène à parler en taille, en distances) . Notons qu'il est déjà possible de calculer p en sommant toutes les tailles des cycles. On obtient toute l’information sur la complexité sous le point de vue précédemment défini, puisque p et l sont toujours liés par la relation p + l = 2^L . Mais tous le détail de l’information sur les chemins est à découvrir. Pour cela, il peut être intéressant de partir de l’autre côté des trajectoires, des Jardins d’Eden.

Nous avons imaginé un détecteur très simple de Jardins d’Eden. Ces derniers correspondent en effet aux générations qui n’ont pas d’antécédents, donc aux générations qui ne sont générations filles d’aucunes générations. Si l’on rentre dans un fichier les générations filles de toutes les générations initiales possibles, les seules générations qui n’apparaissent pas dans la liste sont les Jardin d’Eden. Il suffit donc d’éliminer les doublets de la liste et de l’ordonner pour obtenir une liste exploitable qu’un petit programme pourra balayer en détectant les absences. On a ainsi obtenu une liste des Jardins d’Eden.

Il est aisé de regrouper les Jardins d’Eden par classe d’équivalence correspondant au cycle auquel ils mènent (il suffit de faire tourner jusqu’à arriver à une des générations caractéristiques de cycles).

Les méthodes pour relier Jardins d’Eden et cycles et surtout pour traiter les confluents est complexe. Mais on a déjà réussi à diviser le problème. Le reste de la tache consiste à générer les chemins menant à un seul cycle.

A. 3. Probabilité d'arriver à un cycle donné

La vision cartographique permet de trouver des mesures relatives à un cycle. On peut déjà imaginer sommer les longueurs chemins menant à un cycle et obtenir l(i) et avec la taille du cycle : p(i), les cycles C(i) étant numérotés de 1 à n. Et il est également possible de parler de répartition entre complexité transitoire et établie au niveau d’un cycle.

Une notion qui peut être développée à partir du moment où les cycles ont été différenciés est la probabilité d’un ACL d’arriver sur un cycle particulier. Si on considère que toutes les générations initiales sont équiprobables, cette probabilité est le rapport entre le nombre de génération initiales menant au cycle sur le nombre total de générations initiales. C’est donc le cardinal de l’ensemble des générations attachées au cycle i ( p(i) + l(i) ) sur le cardinal de l’ensemble des générations.

Cette notion est bien illustrée par la représentation en mobile. Plaçons sur la carte de l’automate un mobile par génération initiale et regardons le déplacement des mobiles vers les cycles. Au bout d’un moment, tous les mobiles sont sur des cycles, avec parfois (cas non inversible), plusieurs mobiles par générations. C’est le nombre de mobiles présents sur le cycle une fois arrivé le régime permanent de l’ACL divisé par le nombre total de mobiles qui représente « physiquement » cette probabilité.

B. Factorisations de règle

On prend a, b, c Î Z₂ = { 0 , 1 }

On définit B = R(a , b , c) avec R une règle d'automate cellulaire.

a	b	c
	B

On notera a = a , b = …

On désignera par + l'opérateur OU[1]

par * l'opérateur ET

B. 1. Représentation booléenne des règles

La Règle 105

On a vu que une règle était entièrement définie par la donnée du tableau de la règle. Par exemple la règle 105, inversible parfois:

> rset

No >>105

# # Rule: 105 (01101001)

# # 000-1 001-0 010-0 011-1

# # 100-0 101-1 110-1 111-0

En terme de fonction booléenne on peut l'écrire de la façon suivante:

B = R(a,b,c) = abc + abc + abc + abc

Naturellement, on peut penser à factoriser l'expression:

R(a,b,c) = a ( bc + bc ) + a ( bc + bc ) suivant 'a'

= b ( ac + ac ) + b ( ac + ac ) suivant 'b'

= c ( ab + ab ) + c ( ab + ab ) suivant 'c'

On ne peut plus factoriser: Dans chaque parenthèse chaque élément n'est associé qu'avec son complémentaire. Mais il existe certainement des cas où l'on peut factoriser plus avant…

La Règle Identité

> rs-tab

Break with no change : 9

Break with change kept : 8

0 : 000->0 >> 0

1 : 001->0 >> 0

2 : 010->0 >> 1

3 : 011->0 >> 1

4 : 100->0 >> 0

5 : 101->0 >> 0

6 : 110->0 >> 1

7 : 111->0 >> 1

# # Rule: 204 (11001100)

# # 000-0 001-0 010-1 011-1

# # 100-0 101-0 110-1 111-1

En booléen:

[204](a,b,c) = abc + abc + abc + abc

= b (ac + ac + ac + ac )

= b * (1)

= b

Dans ce cas, quelque soit la variable par la quelle on factorise on aboutira toujours à [204](a,b,c) = b.

La Règle 176

> rset

# # Rule: 176 (10110000)

# # 000-0 001-0 010-0 011-0

# # 100-1 101-1 110-0 111-1

Procédons à une analyse détaillée de la factorisation de la règle:

Règle 176
abc + abc + abc	a ( bc + bc + bc )	a ( c + bc )
		a ( b + bc )

	b ( ac + ac ) + abc	b ( ac + ac ) + abc
		ba + abc

	c ( ab + ab ) + abc	c ( ab + ab ) + abc
		ca +abc

Voici un exemple de l'évolution de cette règle sous Autom3:

> .run

|>g g g g g g g g g g g g g g g g <| 0

|> g g g g g g g g g g g g g g g g <| 1

|> g g g g g g g g g g g g g g g g<| 2

|>g g g g g g g g g g g g g g g g <| 3

|> g g g g g g g g g g g g g g g g<| 4

|>g g g g g g g g g g g g g g g g <| 5

|> g g g g g g g g g g g g g g g g<| 6

|>g g g g g g g g g g g g g g g g <| 7

|> g g g g g g g g g g g g g g g g<| 8

|>g g g g g g g g g g g g g g g g <| 9

|> g g g g g g g g g g g g g g g g <| 10

|> g g g g g g g g g g g g g g g g<| 11

|>g g g g g g g g g g g g g g g g <| 12

|> g g g g g g g g g g g g g g g g<| 13

|>g g g g g g g g g g g g g g g g <| 14

|> g g g g g g g g g g g g g g g g<| 15

|>g g g g g g g g g g g g g g g g <| 16

|> g g g g g g g g g g g g g g g g<| 17

|>g g g g g g g g g g g g g g g g <| 18

|> g g g g g g g g g g g g g g g g<| 19

On est en droit de se demander si [176] n'est pas tout simplement le shift droit.

Vérifions:

> rs-tab

Break with no change : 9

Break with change kept : 8

0 : 000->0 >> 0

1 : 001->0 >> 0

2 : 010->0 >> 0

3 : 011->0 >> 0

4 : 100->1 >> 1

5 : 101->1 >> 1

6 : 110->0 >> 1

7 : 111->1 >> 1

# # Rule: 240 (11110000)

# # 000-0 001-0 010-0 011-0

# # 100-1 101-1 110-1 111-1

[240] se factorise de la façon suivante:

[240](a,b,c) = abc + abc + abc + abc

= a (bc + bc + bc + bc)

= a

On reconnaît le shift droit.

La factorisation de [176] suivant a donne:

[176](a,b,c) = a ( c + bc )

= a ( b + bc )

On voit bien que a a une importance prédominante, mais à cause du facteur {( c + bc ) , ( b + bc )} on peut retomber sur 0 alors que a=1 contrairement à [240].

Notion de degré de factorisation

Les règles de rayon 1 agissent sur des triplets. Il y a donc n = 3! = 6 chemins de factorisation possibles.

Exemple : abc , bca , acb …

On a vu précédemment que:

- les règles 204 et 240 possèdent une seule factorisation, par tous les chemins de factorisation

- la règle 105 en possède trois distinctes

- la règle 176 en possède six distinctes.

Les mots en gras représente le degré de factorisation de la règle.

Il faut considérer chacune des factorisations distinctes comme un angle de vue parmi d'autres pour aborder le comportement de l'automate:

Règle 176		Fact. distinctes	Angles de vue
abc + abc + abc	a ( bc + bc + bc )	a ( c + bc )	a =0 imposé	Influence de a
		a ( b + bc )

	b ( ac + ac ) + abc	b ( ac + ac ) + abc	b = 1 => ac	Influence de b
		ba + abc	b = 0 => a

	c ( ab + ab ) + abc	c ( ab + ab ) + abc	c = 0 => ab	Influence de c
		ca +abc	c = 1 => a

En fait le choix du chemin de factorisation détermine le "degré d'importance" que l'on va accorder à chaque variable. On commence à sentir l'intérêt des deux types d'information que nous délivre une factorisation totale (sur tous les chemins):

- Un certain nombre de formules factorisées, donc simplifiées.

- Le nombre de formules distinctes, dont intuitivement on conçoit le rapport avec les mesures de complexité.

Cependant la factorisation à la main est longue et devient quasiment impossible dès que le rayon augmente. Il faut trouver un moyen d'automatiser le processus.

B. 2. Un algorithme de factorisation des règles de rayon r

Quand nous nous sommes penchés sur cette notion de factorisation, nous avons créé un algorithme de factorisation optimisé pour cet usage.

Cet algorithme pourra être utilisé dans la conception d'outils d'étude de la factorisation. il est également intéressant du point de vue théorique, car il fait intervenir un automate cellulaire très particulier.

Principe de l'algorithme

On admet que l'algorithme que nous allons décrire est inséré dans un programme qui teste les (2 r +1)! chemins possibles et que l'on a déjà décidé du chemin. Par simplicité on prendra le chemin a-b-c. Le problème est aisément transposable dans un autre cas.

Notre donnée est un tableau de 2^2r+1 (0) et (1): le code de la règle.

Notre objectif est de créer une structure qui permettra à un autre programme, la lisant simplement, de reconstituer la formule.

Cette structure est un arbre binaire de taille 2r+1:

Arbre:

Nous allons créer un automate cellulaire de dimension "arbre" (chaque case possède trois interfaces avec les autres), qui va remonter l'arbre et inscrire des chiffres dans les cases.

Cet automate constructeur ne peut pas descendre sur l'arbre, il est en fait de dimension 1 dans la dimension "graphe": Le sommet supérieur de chaque triangle est la conséquence des valeurs des deux sommets de la base.

Enfin, chaque case du graphe est repérée par un produit booléen (ici dans le cas du chemin a-b-c):

Racine

/b/

abc

abc

L'Automate Cellulaire Constructeur

On remplit les cellules de base du graphe par les valeurs du code de la règle. et on applique l'automate constructeur dont la règle est décrite dans le tableau ci-dessous:

	0	1	2	3
0	0	2	2	2
1	2	1	3	3
2	2	3	3	3
3	2	3	3	3

L'automate constructeur est donc un automate à quatre états. Pour l'instant ces valeurs ne signifie rien, c'est le Lecteur qui va les interpréter et donner les ordres nécessaire à la création de la formule.

On notera que le tableau est symétrique: l'ordre n'intervient pas.

Donnons nous [54]:

> rset

No >>54

# # Rule: 54 (00110110)

# # 000-0 001-1 010-1 011-0

# # 100-1 101-1 110-0 111-0

La base du graphe binaire devient :



0	1	1	0	1	1	0	0

On applique l'automate constructeur:

3

3				2

2		2		1		0

0	1	1	0	1	1	0	0

Le Lecteur

Ce programme[2] se déplace sur le graphe en effectuant à chaque case une action et une redirection.

Une redirection détermine la case à laquelle se rendra le Lecteur ensuite.

Seulement deux directions sur les quatre possibles sont autorisées: Suivant (S) et Raccourci (R).

On distingue deux types de configuration:

: R

:Type I

: R

:Type 2

: S

Les actions consiste à insérer des caractères dans une chaîne qui constituera la formule.

Pour une case c, on définit:

- val( c ) : valeur de la case (initialisée par l'automate constructeur)

- car( c ) : le caractère associée à la case (ci-dessous pour le chemin a-b-c)

Voici le programme d'action du Lecteur:

val( c )	Insertion	Redirection
0	Æ	R
1	car( c ) +	R
2	car( c )	S
3	car( c ) x [ ou ]	S

On obtient ainsi, pour chaque chemin, la formule factorisée de la règle.

Bilan

Du point de vue algorithmique, tous les problèmes semblent résolus. Le processus décrit est indépendant du rayon. C'est à dire que quelque soit la taille du voisinage, cet algorithme et capale de façon systèmatique de factoriser l'automate.

Cependant certains aspects de la programmation, tels que la construction du graphe ou le déplacement du Lecteur, seront certainement délicats à aborder.

Il faut également rester conscient que le type de factorisation auquel s'intéresse cette étude n'est pas le seul.

Il manque la composante introduite par l'équation suivante:

C'est à dire que certaines règles pourrait s'écrire très simplement et garder quand même une forme relativement complexe à travers cet algorithme (Exemple : R(a,b,c) = a + b )

L'algorithme présenté ici n'est qu'une première approche de la programmation des différents types de factorisation.

B. 3. Perspectives ouvertes par les notions de factorisation

On a vu que la factorisation permettait de se représenter l'influence d'une suite ordonnée de variables (le chemin de factorisation) sur le résultat fourni par l'automate.

Deux perspective s'offrent alors:

Classification - Mesure de complexité

On peut espérer mesurer un certain aspect de la complexité par l'ordre de factorisation de la règle. En effet si on reprend les résultats du C. 1. :

- les règles 204 et 240 possèdent une seule factorisation, par tous les chemins de factorisation

- la règle 105 en possède trois distinctes

- la règle 176 en possède six distinctes.

On remarque que[204] et [240] sont toutes deux des règles inversibles, [205] est la règle d'un ACL inversible parfois et [176] n'est ni l'un ni l'autre.

Peut être est-ce une coïncidence…

Cependant, si on dénombre les règles d'ordre 1, il ne peut en y avoir que 6 et ce sont les six règles inversibles.

Différentiabilité sur les règles

On pourrait définir la factorisation d'une règle par rapport à un chemin de variable. Si on trouve une façon de mesurer la "complexité intrinsèque" de la formule obtenue on disposerait ainsi d'une pseudo-différentiabilité sur les règles. Cette voie n'est encore qu'une simple vue de l'esprit

Accélération du calcul des générations

Dans le cadre du développement d'une plate-forme d'étude informatique, l'aspect simplificateur des factorisations pourrait permettre de "pré-compiler" la règle de l'automate avant chaque calcul de façon à optimiser le nombre d'opérations effectuées.

Lors de longs calculs balayant tous les ACL le gain pourrait être très intéressant.

Conclusion

L'étude de la factorisation des règles d'automates cellulaires permet d'obtenir des informations précises et parlantes sur le comportement d'un automate. Ces informations sont de plus indépendantes de la largeur des générations sur lesquelles s'appliquent ces règles.

De nombreuses voies restent à explorer mais il semble d'ors et déjà que la factorisation pourrait être un outil utile, si ce n'est indispensable, dans l'étude des règles de grand rayon.

C. Vers une topologie de la complexité?

Un des enjeux majeurs de l'étude des automates cellulaires est de déterminer des mesures fiables pour approcher le concept de complexité. De ces mesures on peut facilement espérer tirer des distances sur les espaces considérés et les munir ainsi d'une structure topologique. La question serait alors de savoir sous quelle forme visualiser ces structures.

C. 1. Particularités du concept de complexité

La notion de complexité qui est omniprésente dans cette étude est au départ une notion intuitive. Considérons les trois règles ci-dessous en largeur 10 appliquées à la même génération initiale (non représentée).

Les habituels carrés ont été remplacés par des traits pour montrer que (0) et (1) sont au même niveau.

Règle 51

Règle 150

Règle 240

> .run

|> _ _ ____<| 0

|>_ __ _ <| 1

|> _ _ ____<| 2

|>_ __ _ <| 3

|> _ _ ____<| 4

|>_ __ _ <| 5

|> _ _ ____<| 6

|>_ __ _ <| 7

|> _ _ ____<| 8

|>_ __ _ <| 9

|> _ _ ____<| 10

|>_ __ _ <| 11

|> _ _ ____<| 12

|>_ __ _ <| 13

|> _ _ ____<| 14

|>_ __ _ <| 15

|> _ _ ____<| 16

|>_ __ _ <| 17

|> _ _ ____<| 18

|>_ __ _ <| 19

> .run

|>_ __ _<| 0

|> _ _ __ <| 1

|>_______ _<| 2

|>______ __ <| 3

|> ____ <| 4

|>_ __ _ <| 5

|>_ __ _<| 6

|> _ _ __ <| 7

|>_______ _<| 8

|>______ __ <| 9

|> ____ <| 10

|>_ __ _ <| 11

|>_ __ _<| 12

|> _ _ __ <| 13

|>_______ _<| 14

|>______ __ <| 15

|> ____ <| 16

|>_ __ _ <| 17

|>_ __ _<| 18

|> _ _ __ <| 19

> .run

|> _ __ _ <| 0

|> _ __ _ <| 1

|> _ __ _ <| 2

|> _ __ _<| 3

|>_ _ __ <| 4

|> _ _ __<| 5

|>_ _ _ _<| 6

|>__ _ _ <| 7

|> __ _ _<| 8

|>_ __ _ <| 9

|> _ __ _ <| 10

|> _ __ _ <| 11

|> _ __ _ <| 12

|> _ __ _<| 13

|>_ _ __ <| 14

|> _ _ __<| 15

|>_ _ _ _<| 16

|>__ _ _ <| 17

|> __ _ _<| 18

|>_ __ _ <| 19

Peut on dire que ces trois graphes offrent la même complexité? Si on demandait à un grand nombre de personnes de choisir un ordre, lequel serait le plus cité?

La classification de Wolfram est une première réponse. Dans cet exemple, [51] et [240] sont de classe 2 et [150] de classe 3. Mais on perçoit cependant rapidement les limites d'une différenciation purement intuitive et on est amené à chercher des grandeurs à mesurer dont l'évolution est cohérente avec la représentation intuitive que l'on se fait de la complexité.

Notre première piste fut le degré de factorisation d'une règle. Sans fournir une véritable mesure, il permettait un classement non arbitraire des règles. Nous abandonnâmes cette voie pour nous intéresser aux cycles des ACL.

L'importance de deux grandeurs s'imposa petit à petit. Nous nous y intéressâmes en tant que mesure de la complexité.

Une première remise en cause fut d'admettre que la complexité comportait deux composantes:

- une composante transitoire : tau, le temps d'arrivée à un cycle

- une composante permanente : T, la période du cycle

Les premiers résultats confirmèrent la pertinence d'une telle approche: Un ACL est inversible si et seulement si pour chacun de ses cycles tau = 0 (cf. Partie 2).

Quand par la suite nous nous intéressâmes aux cartes d'ACL, nous introduisîmes de nouvelles mesures, issues de tau et T mais spécifiquement adaptées aux ACL. En effet, il s'avère de plus en plus que parler de la complexité en tant que telle n'a pas tellement de sens: il faut parler de la complexité d'une règle ou d'un ACL ou d'une génération ou d'une formule de factorisation…

Après avoir défini avec précision l'espace dans lequel on se place, on cherche les valeurs quantifiables qui illustre le mieux la représentation intuitive que l'on se fait de la complexité de l'objet. On cherchera bien sûr celles qui sont cohérentes avec les cas extrêmes.

C. 2. Quelles structures topologiques ?

Notre réflexion sur la topologie des espaces liés aux automates cellulaires en est actuellement au stade (élémentaire) de la recherche d'une distance. On espère en effet pouvoir faire dériver un type de distance d'un espace à l'autre.

Par exemple on peut s'intéresser, pour une génération initiale donnée, à taum = moyenne des tau des cycles des 256 ACL. On conçoit bien que une génération initiale donnée "complexe" mettra plus de temps à arriver à un cycle que une "simple".

On peut ensuite ramener à zéro les plus basses valeurs et obtenir ainsi une distance au sens de la complexité.

Cette distances, assez cohérentes aux extrêmes, n'a pas encore pu prouver sa pertinence.

En admettant que l'on dispose d'une distance au sens de la complexité sur l'ensemble des générations initiales (c'est à dire les Largeur-uplets de (0) et de (1)), on pourrait espérer faire de l'analyse sur les fonctions que sont les ACL.

C. 3. Représentations des espaces liés aux ACL

Une fois muni des mesures adéquates il est tentant de chercher à organiser de façon cohérente (c'est à dire quantifiée et ordonnée) les espaces d'ACL ou les ACL eux-mêmes.

On peut privilégier une vision cartographique au risque de sacrifier la rigueur à la lisibilité ou se tourner vers une formalisation multidimensionnelle uniquement informatique.

Comme souvent dans le domaine des automates cellulaires nulle doute que c'est une méthode intermédiaire qui s'imposera exploitant cette fois les capacités graphiques des ordinateurs actuels.

[1] on verra que la distinction OU exclusif ou non n'a pas d'importance dans le cadre de cette étude, tous les cas étant disjoints.

[2] en réalité un automate cellulaire de dimension "graphe" dégénéré