Les Automates Cellulaires

 

 

 

Introduction :

C’est Von Neumann qui dans les années 50 a le premier développé le concept des automates cellulaires. Ses motivations étaient philosophiques : il voulait prouver que l’idée d’une machine pouvant créer des copies exactes d’elles-mêmes n’étaient pas logiquement contradictoires et ne nécessitaient rien d’autre que des mécanismes de calculs élémentaires comme ceux qu’utilisent les automates.

Un jeu comme le Jeu de la Vie a ensuite joué un grand rôle dans la diffusion et surtout la vulgarisation de ce concept.

Par la suite, les automates cellulaires se sont divisés en deux grandes classes : les automates cellulaires actifs (du type Von Neumann) et les automates passifs, particulièrement utilisés en modélisation physique.



I. Le Jeu de la Vie

Le Jeu de la Vie est une bonne illustration d’un automate cellulaire simple. Créé par John Horton Conway (Cambridge University) en 1970, ce jeu a connu un grand succès du fait de sa simplicité, sa mise en oeuvre informatique aisée et les développements variés auxquels il a donné lieu.

Les règles en sont les suivantes :

Il se joue sur un damier infini, sur les cases duquel sont disposés des pions représentant les cellules d’un organisme. Ces cellules naissent, meurent ou survivent à chaque génération selon des règles bien précises. Conway a choisi ces règles après de nombreuses expériences, de sorte que l’évolution de ces organismes soit assez imprévisible, notamment en ce qui concerne leur disparition, leur caractère périodique ou leur croissance infinie.

1- Survie

Toute cellule ayant exactement deux ou trois cellules voisines survit à la génération suivante.


2- Mort

Toute cellule ayant quatre cellules voisines ou plus meurt par étouffement à la génération suivante. Une cellule isolée ou n’ayant qu’un seule cellule voisine meurt d’isolement à la génération suivante.

 

3- Naissance

Sur une case vide comportant exactement trois cellules voisines, il naît une cellule à la génération suivante.

 

On peut faire deux remarques importantes :

II Cas général : les automates cellulaires


1- Caractéristiques

Les automates cellulaires peuvent avoir de nombreux états possibles : au lieu de n’avoir que l’état « mort » ou l’état « vivant » pour une cellule, on peut définir autant d’état que l’on souhaite (que l’on peut modéliser à l’écran par des couleurs par exemple). John Von Neumann a par exemple étudié mathématiquement un automate à vingt-neuf états.

De plus, on peut choisir des règles de nombreuses sortes de règles de transition d’une génération à l’autre. En outre, on peut aussi modifier le voisinage utile de l’automate, c’est à dire dans le cas précédent ne plus tenir compte de huit voisines, mais quatre ou douze... Le voisinage utile étant les cases utilisées dans la règle de transition.

On peut d’autre part utiliser des cellules de géométries multiples. Il peut être ainsi intéressant d’utiliser des cases hexagonales (« nids d’abeilles »).


2- Quelques propriétés remarquables

La reproduction

Le but de Von Neumann, à l’origine, lorsqu’il a conçu le principe des automates cellulaires, était de concevoir un mécanisme copiant la vie dans le sens où il pourrait se reproduire de lui même.

Ainsi certains automates cellulaires sont capables de produire des copies d’eux-mêmes, propriété particulièrement intéressante lorsqu’il s’agit de modéliser la vie d’êtres vivants. Ce point de vue de la reproduction permet de classer les automates cellulaires en deux grandes catégories :
· les automates cellulaires actifs, c’est à dire auto-reproducteurs.
· les automates cellulaires passifs.

Les automates cellulaires actifs sont auto-reproducteurs dans le sens où ils contiennent une sous-configuration qui se comporte en « copieur universel » dirigeant activement la réplication via une fonction de transition assurant la réplication.

Les automates cellulaires passifs sont ainsi nommés car leur reproduction est provoqué par la règle de transition et non pas par les caractéristiques de la configuration initiale. Le Jeu de la Vie est un exemple d’automate cellulaire passif.

L’inversibilité

On appelle automate inverse l’automate qui permet de revenir aux états précédents.

Un exemple simple d’automate inverse est celui de l’automate déplacement Est. Chaque case peut avoir deux états, 0 et 1 (vide ou plein). L’automate regarde l’état de la case voisine Ouest, s’en souvient et agit en le prenant pour nouvel état de la case. Un réseau d’automates Déplacement Est sur un plan a pour effet, d’une génération à l’autre, de déplacer d’une case vers l’Est le motif initial. Son inverse est l’automate Déplacement Ouest.

Cet automate possède deux états : 0 et 1, représentés l'un par une case blanche, l'autre par une case noire. D'une génération à l'autre, chaque automate du réseau regarde l'état de son voisin Ouest et le prend pour lui-même. Le résultat est qe le dessin se déplace vers l'Est.

On a démontré que tous les automates n’ont pas nécessairement un inverse. Pour démontrer qu’un automate n’a pas d’inverse il suffit de trouver deux configurations différentes qui aboutissent à la même configuration.

Cet automate, utilisant les règles du jeu de la vie, commence par un pentamino et évolue en 11 étapes. Au bout de la onzième l'étape 12 est la même que la dixième. On a donc deux configurations différentes qui donnent la même : l'automate de Conway (qui est celui du jeu de la vie) n'est pas inversible.

La question qui se pose alors est, lorsqu’on a construit un automate, de savoir si celui-ci est inversible. Et bien cette question est un problème indécidable.

L' ’indécidabilité

L’une des caractéristiques importantes des automates cellulaires est le caractère d’indécidabilité qui touche nombre de leurs propriétés.

Ainsi, déterminer si un automate cellulaire possède un inverse est indécidable : il ne sera jamais possible d’écrire un programme prenant en paramètres un automate quelconque et pouvant décider si oui ou non cet automate possède un inverse.

De la même façon, l’« avenir » d’un automate est indécidable. On n’a pas de méthode générale permettant de déterminer si un automate ne va pas s’éteindre au bout d’un certain nombre de générations ou s’il va se stabiliser

Les Jardins d’Eden

Un Jardin d’Eden est une configuration qui ne possède pas d’antécédent. Cela ne se produit bien entendu pas avec les automates inversibles. De même, par exemple, une configuration Jardin d’Eden ne peut être un attracteur car elle ne peut apparaître que comme première configuration d’une suite de configurations. L’aspect remarquable de ce concept est que la question de l’existence de Jardins d’Eden est indécidable. Cela a été démontré par J. Kari en 1990.

Un autre résultat intéressant avait déjà été trouvé en 1962 par E. Moore et J. Myhill : un automate possède des Jardins d’Eden si et seulement si deux configurations finies donnent le même résultat. Cette précision pour souligner le fait que cette question a su tenir en haleine les informaticiens, et peut-être plus généralement, les logiciens pendant longtemps.

Cette configuration n'a pas de prédecesseur : c'est un jardin d'Eden.

Les attracteurs

Les attracteurs des automates sont des configurations qui reviennent indéfiniment. Etant des cas particuliers d’automates , ils permettent des études intéressantes sur les automates et la démonstration de propriétés.

Ainsi, J. Kari a démontré que toute propriété de l’ensemble limite (l’ensemble des attracteurs) est vraie pour certains automates et fausses pour d’autres est indécidable. Ce résultat est finalement le plus extraordinaire de tous, car il nous montre que nous ne saurons jamais rien à l’infini des réseaux d’automates cellulaires.


3- Quelques exemples importants

Le glisseur est une configuration du Jeu de la Vie qui, en quatre générations, se déplace d’une case le long d’une diagonale.

Le lance-glisseurs est une configuration qui, toutes les N générations, produit un glisseur qui s’échappe.

III Applications

Applications physiques

L’idée principale est d’effectuer un modèle discret de l’Univers, plus facile à gérer qu’un modèle continu. Une représentation simpliste en celle des éléments finis, avec un découpage vraiment élémentaire.

Les automates cellulaires permettent d’une façon très performante la simulation de fluides turbulents, chaque particule jouant le rôle d’une cellule. On peut aussi simuler la croissance de cristaux en se servant des règles d’agencement d’une molécule avec ses plus proches voisines. Les techniques d’approche sont sensiblement les mêmes : on observe le comportement des automates les uns par rapport aux autres de la même façon que des cristaux interagissent.

L’avantage de l’utilisation des automates cellulaires est que cela évite de passer par l’intermédiaire équations différentielles ou des équations aux dérivées partielles.

Dans le domaine de la simulation quantique et probabiliste, les automates cellulaires se révèlent utiles car il suffit d’introduire un facteur probabiliste dans les états accessibles. Le problème est le même pour approcher la percolation. Les particules possèdent des probabilités d’évolution dans le milieu qu’elles traversent.

Il est assez raisonnable de soutenir de tels modèles, car à l’étape ultime de l’observation, c’est à dire au niveau atomique, la matière a un aspect plus proche d’entités discrètes - modélisables par des automates - que d’un continuum. La modélisation par des automates se présente donc comme une technique d’avenir qui devrait à terme supplanter la classique modélisation continue.


Applications informatiques

En cryptographie, il est possible de décoder des messages en les parcourant à l’aide d’un automate qui va par exemple repérer l’occurence de certains motifs. On peut alors rafiner le système de reconnaissance en y ajoutant des probabilités de présence de certains motifs dont peut être coutumier le producteur du code.

Exemple de codage d'un message par un automate cellulaire. Cette photo est tirée du numéro 169 de Pour la Science (Novembre 1991)

Sans doute la découverte la plus essentielle sur les automates est elle celle de James Conway. Il démontré qu’il est possible d’associer des automates pour fabriquer une machine de Turing. Cela acquis, on peut intégralement fabriquer un ordinateur à partir de tels automates. Un des challenges est alors de disposer un nombre suffisant de semi-conducteurs sur une seule puce.

Une dernière application concerne le calcul massivement parallèle : on fait fonctionner un certain nombre d’automates en parallèle, l’intérêt étant une communication aisée entre voisins.

Conclusion :

Les automates sont un développement relativement récent de la science moderne. Extrêmement vaste et complexe à étudier, bien que facilement modélisable sur ordinateur, cette discipline est promise à un grand avenir car elle permet de modéliser de façon pratique et simple de nombreux phénomènes physiques. De plus, les « curiosités » mathématiques et philosophiques qu’elles soulèvent font d’elle un domaine passionnant pour les chercheurs.

Comme cela a été développé, il s’agit d’autre part d’une nouvelle technique de modélisation qui rompt avec la tradition continue. La mécanique quantique ayant mis en avant, parallèlement à nos connaissances de l’atome un monde appréhendable de façon discrète, il est tentant de se laisser aller à rêver d’un univers, gigantesque automate cellulaire dont la nature calculerait à chaque instant l’évolution.


Bibliographie : Le numéro 191 de Pour la Science et nos prédecesseurs aux Mines sur ce sujet

Home