Prenons une feuille à petits carreaux et un crayon à papier. Noircissons la case du milieu de la première ligne. Sur la ligne suivante, noircissons une case seulement si la case au dessus à droite ou la case au dessus à gauche est noire. Réitérons avec les lignes suivantes jusqu’à épuisement. Le résultat est étonnamment complexe et esthétique considérant la simplicité du procédé !
Le résultat de notre dessin méthodique est une fractale: le triangle de Sierpiński
Le procédé que nous avons utilisé s’apparente à un automate cellulaire élémentaire.
Automates cellulaires
Un automate cellulaire est constitué de cellules, généralement disposées de manière régulière, contenant chacune un état donné parmi un ensemble fini. L’automate évolue en fonction du temps de manière discrète. L’état d’une cellule au temps t+1 dépend de l’état au temps t d’un nombre fini de cellules proches d’elles (et pouvant l’inclure) appelé son voisinage. À chaque nouvelle étape, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle génération de cellules dépendant entièrement de la génération précédente.
Si les cellules sont disposées sur une ligne, l’automate cellulaire est à une dimension. Sur un plan, l’automate serait à deux dimensions. Dans l’espace, il serait à trois dimensions … Dans notre exemple, l’automate avait une seule dimension.
Le voisinage peut être plus ou moins grand. Dans notre cas, le voisinage d’une cellule est constitué de trois cellules: celle à sa droite, elle-même et celle à sa gauche. Les automates cellulaires à une dimension ayant un voisinage plus petit n’ont pas un grand intérêt. Composé seulement de la cellule elle même, l’automate serait soit stationnaire (ne changeant pas dans le temps) soit alternerait entre deux configurations. Composé de deux cellules, il pourrait être intéressant mais il existe un automate avec un voisinage de trois cellule qui est strictement identique.
Enfin, notre automate n’a que deux états: case noire ou case blanche. Ici encore, on ne peut faire plus simple sans tomber sur un automate sans intérêt !
Les automates cellulaires à une dimension, utilisant un voisinage de 3 cellules et ne comptant que deux états sont appelés automates cellulaires élémentaires.
Étude systématique des automates cellulaires
Combien existe-t-il d’automates cellulaires élémentaires ? Ce qui définit l’automate, c’est l’ensemble des transitions possible du temps t au temps t+1. Dans le cas élémentaire, le voisinage comporte 3 cellules qui peuvent chacune prendre 2 états. Il y a donc 23 = 8 configurations possibles pour le voisinage. Pour définir complètement le fonctionnement de l’automate, il faut donc donner les 8 valeurs d’état de la cellule correspondant au 8 états possibles de son voisinage.
Il est donc possible de définir 28 = 256 automates cellulaires élémentaires en donnant un état parmi les deux possibles pour chaque combinaison d’états possibles dans le voisinage.
D’une manière plus générale, pour un type d’automates avec un voisinage comptant n cellules et comportant p états, il existe ppn automates.
| 2 états | 3 états | 4 états | 5 états | |
|---|---|---|---|---|
| 2 voisins | 16 | 19 683 | 4,29.109 | 2,98.1017 |
| 3 voisins | 256 | 7,63.1012 | 3,40.1038 | 2,35.1087 |
| 4 voisins | 65 536 | 4,43.1038 | 1,34.10154 | 7,18.10437 |
| 5 voisins | 4,29.109 | 8,72.10115 | 3,23.10617 | 1,91.102186 |
Ces nombres sont tout simplement gigantesques. Même en tenant compte des symétries et des permutations d’états, il est impossible d’étudier de manière systématique les automates à 4 états ou plus, les automates à 3 états ayant une taille de voisinage de 3 ou plus ni les automates à 2 états ayant 5 voisins ou plus.
Mais l’étude systématique des automates élémentaires est possible et très intéressante, malgré leur apparente simplicité.
La notation de Wolfram
Il existe une numérotation très pratique des automates cellulaires élémentaires. L’automate étant défini par la liste des transitions, on peut attribuer à chaque automate le numéro correspondant à la représentation en base 2 (le nombre d’états) dans un ordre des configuration de voisinage prédéfini (l’ordre décroissant du voisinage par convention). Par exemple pour notre exemple initial, la cellule ne prend l’état 1 à l’instant t+1 que si le voisinage à l’instant t était 100 ou 001 (cellule de gauche ou cellule de droite noircie):
| Voisinage à t | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Etat à t+1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
00010010 en binaire vaut 18. Cet automate correspond donc à la règle 18.
Cette notation peut bien sûr être étendue aux automates ayant des voisinages plus grand où un nombre d’états plus élevé (en utilisant la base correspondant au nombre d’états).
Rêgles symetriques
Parmi les 256 automates cellulaires élémentaires, certains sont équivalents.
| Voisinage à t | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Règle 10 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| Règle 80 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
La règle 10 et la règle 80 par exemple, sont symétriques par réflexion par rapport à un axe vertical. Parmi les 256 règles, 64 sont leur propre symétrique selon cette symétrie là. Il y a donc 96 règles que l’ont peut écarter. Il n’en reste donc plus que 160 à étudier !
Une autre forme de symétrie est la complémentarité. On peut échanger les rôles des 0 et des 1. Par exemple, pour construire le complémentaire de la règle 10, commençons par le voisinage 111. Son complémentaire est le voisinage 000 qui dans la règle 10, aboutit à l’état 0. On complémente cet état d’arrivé aussi. Dans le complémentaire de la règle 10, le voisinage 111 aboutira donc à l’état 1. On procède de même pour chaque voisinage.
| Voisinage à t | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Règle 10 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| Règle 175 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
Enfin, on peut combiner les deux symétries pour trouver une troisième symétrie permettant d’éliminer encore quelque règle. La règle 10 a par exemple la règle 245 pour symétrique complémentaire:
| Voisinage à t | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Règle 10 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| Règle 245 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
Au final, seules 88 règles sont réellement distinctes une fois pris en compte ces trois types de symétrie.
Configuration initiale unitaire
Une méthode pour étudier les automates cellulaires est d’utiliser une configuration initiale avec une seule cellule dans l’état 1 et toutes les autres dans l’état 0. On peut, pour les règles paires (qui ne transforment pas le voisinage 000 en 1) interpréter le résultat à chaque instant comme un nombre en base 2 et étudier la suite ainsi produite. Certaines sont triviales, comme la règle 2 qui produit la suite des puissances de 2 (c’est à dire la suite u(n) = 2n). D’autres sont bien plus complexes, comme la règle 110.
Ces suites peuvent être obtenues avec le programme ci-dessous en utilisant la configuration initiale appropriée à la règle étudiée (appuyer sur A, Z ou E) puis en appuyant sur D. Si l’anglais ne vous fait pas peur, vous pouvez taper les premiers nombres obtenus dans le champs de recherche de https://oeis.org. Il est intéressant de constater que la quasi totalité des suites peuvent être définies d’une autre manière (la règle 110 semble être une exception). Attention, il faut parfois aller assez loin pour trouver la bonne suite. Par exemple, les 32 premiers nombres produits par la règle 102 correspondent à 3 suites référencées. Seul le 33ème nombre permet de déterminer la bonne.
Programme
Voici un programme en python permettant d’observer les automates cellulaires élémentaires en action.
Les commandes suivantes sont disponibles:
- Bouton gauche de la souris: passer la cellule pointée à l’état 1 au temps t=0
- Bouton droit de la souris: passer la cellule pointée à l’état 0 au temps t=0
- P: passer à l’automate suivant (règle + 1)
- M: passer à l’automate précédent (règle – 1)
- A: état initial avec une seule cellule à 1, à l’extrême gauche
- Z: état initial avec une seule cellule à 1, au centre
- E: état initial avec une seule cellule à 1, à l’extrême droite
- R: état initial aléatoire
- N: état initial régulier (alternance de 0 et de 1, mais à changer dans le code pour vous amuser !)
- I: afficher ou masquer l’information (numéro de la règle et représentation binaire en bas à droite)
- D: Afficher les nombres correspondant aux lignes successives de l’automate
- Espace: réinitialiser l’automate
- Echap: quitter
Quelques automates notables
Automates qui produisent un triangle de Sierpinski: 18, 22, 26, 82, 90, 94, 102, 122, 126, 129, 133, 146, 153, 154, 161, 165, 167, 181, 182, 183, 195, 210, 218
Parmi ces deux, le 154, le 166, le 180 et le 210 ont une propriété intéressante: ils peuvent dessiner un bandeau du triangle seulement. Interessant, deux automates produisent une fractale proche du triangle de Sierpinski: 105 et 150. Ils sont complémentaires l’un de l’autre (105 = 01101001, 150 = 10010110).
Fractale produite par la règle 150
Le Conus Textile est un coquillage dont la carapace rappelle la règle 30
La règle 110 tient une place particulière. En effet, il a été démontré qu’elle est capable d’effectuer des calculs et est Turing-complet, c’est à dire capable d’effectuer tous les calculs que peut faire un ordinateur. Pour ce faire, il faut utiliser un motif régulier comme point de départ et y introduire des irrégularités afin de coder les données d’entrée (algorithmes à exécuter et données). Même les calculs les plus simples sont très complexes à programmer, cet automate n’est donc pas une bonne calculette. Mais qu’une règle si simple présente une telle propriété est impressionnant !
Exemple de motif régulier présentant deux irrégularités dont les influences se rejoignent et interfèrent
Plus d’états
Il n’est pas bien compliqué de modifier le programme ci-dessus pour supporter un plus grand nombre d’états. Comme on l’a vu plus haut, le nombre de règles augmente très rapidement avec le nombre d’états.
Voici le programme en python modifié pour gérer un nombre variable d’états. Les nouvelles commandes en plus des précédentes sont:
- W pour diminuer le nombre d’états
- X pour augmenter le nombre d’états
- C pour choisir une règle au hasard
- Q pour afficher tous les états
- S pour n’afficher qu’un seul état
- F pour que l’état affiché soit le précédent (lorsqu’on affiche un seul état)
- G pour que l’état affiché soit le suivant (lorsqu’on affiche un seul état)
Tout n’est pas géré parfaitement. En particulier, il n’est pas possible de choisir l’état dans lequel on met une cellule à l’aide de la souris, c’est toujours l’état 1 ou l’état 0. Lorsque l’on diminue le nombre d’état, la règle sur laquelle on était peut ne pas exister avec un état de moins et on est donc dans un état un peu bancal (dans ce cas le mieux est d’appuyer sur C !). Cependant, cette version simple permet d’apprécier la complexité qu’amène l’augmentation du nombre d’états.
Exemple d'automate à 4 états. On voit à quel point le numéro de la règle, tout comme sa description, sont longs avec seulement 2 états supplémentaires !
Pour aller plus loin
Sur les automates cellulaires en général:
- http://fr.wikipedia.org/wiki/Automate_cellulaire
- https://interstices.info/jcms/c_19162/la-riche-zoologie-des-automates-cellulaires
- http://promenadesmaths.free.fr/Automates%20cellulaires.htm
- http://www.rouquier.org/jb/research/eca/
Introduire une notion de continuité dans les états d’un automate élémentaire: