L'Univers des automates cellulaires
Durant le Mois de la Science organisé à Neuchâtel par la Société des enseignants neuchâtelois de sciences à la fin de 1995, l'exposition « les nombres et les plantes », hébergée au Musée d'histoire naturelle, offrait un poste de travail permettant aux visiteurs de réaliser des « rideaux », c'est-à-dire des figures construites à partir d'automates cellulaires. Ces pages présentent une brève introduction aux automates cellulaires et rendent compte des travaux laissés par les participants. En particulier, toutes les illustrations sont des créations originales réalisées dans le cadre de cette exposition.
Les mathématiques actuelles abordent depuis quelques années le virage de la « complexité ». Des modèles sont élaborés qui permettent de dépasser les approximations linéaires auxquelles les phénomènes naturels étaient souvent ramenés. L'ordinateur joue un rôle important dans cette perspective et, conjointement, il a introduit un nouveau style d'exploration en mathématique. Parmi ces mathématiques « expérimentales », les procédés qui utilisent la répétition de règles de transition sont simples à mettre en oeuvre. Les résultats obtenus sont souvent spectaculaires dans la mesure où la simulation d'un phénomène global est obtenue à partir de « structures locales de calcul » dans lesquelles le « hasard » tient souvent une grande place.
Parmi ces méthodes, les automates cellulaires occupent une place de choix. Le « jeu de la vie » , imaginé par le mathématicien John Horton Conway en 1970, est un exemple fameux d'automate cellulaire. Plusieurs disciplines se réfèrent à ce modèle: en biologie pour des études d'évolution, en informatique (recherche de machines « universelles », réseaux neuronaux), en physique avec les phénomènes de diffusion et de percolation, etc.
La situation générale est la suivante, on imagine des « cellules » interconnectées. A un moment donné, chaque cellule est caractérisée par son état (une valeur que l'on peut souvent symbolisé par une couleur). L'évolution du système est donné de la façon suivante: l'état d'une cellule au temps t+1 est déterminé par une règle de transition, c'est-à-dire une fonction de l'état de la cellule au temps t et de l'état, au temps t également, des cellules auxquelles elle est connectée.
Dans la pratique, les études sont principalement réalisées avec des réseaux quadrillés ou triangulés. L'interconnexion est donnée par le contact direct des cellules. Sur un réseau quadrillé on considère souvent comme voisinage d'une cellule carrée les quatre cellules ayant un côté en commun (voisinage de von Neumann) ou les huit cellules qui entourent le carré (voisinage de Moore). Le jeu de la vie utilise un voisinage de Moore.
On a de la peine à imaginer comment un dispositif aussi simple peut donner naissance à des phénomènes complexes. On peut toutefois constater que pour des cellules à n états différents ayant chacune v voisines, le nombre de règles s'élève à n n^(v+1). C'est un nombre rapidement énorme. Pour des cellules à 3 états et un voisinage de 4, son code décimal comprend 115 chiffres! Pour des cellules à 3 états et un voisinage de 8, le nombre de règles de transition disponibles s'écrit avec plus de 9000 chiffres!
[ RIDEAUX ][ MATH-ECOLE ]