Un automate cellulaire est un modèle de calcul reposant sur une grille de cases, appelées cellules, dont chacune se trouve dans un état parmi un petit nombre de possibilités, par exemple vivante ou morte, allumée ou éteinte. Le temps y avance par étapes successives, et à chaque étape toutes les cellules changent d’état en même temps selon une même règle, très simple, qui ne tient compte que de l’état de la cellule et de celui de ses voisines immédiates. Aucune coordination centrale ne dirige l’ensemble: chaque cellule ne regarde qu’autour d’elle et applique la règle locale. Le fait remarquable est que, de ces interactions purement locales répétées un grand nombre de fois, peuvent émerger à l’échelle de toute la grille des comportements d’une richesse et d’une complexité stupéfiantes, sans commune mesure avec la simplicité des règles de départ.
Ce modèle a été imaginé dans les années 1940 par John von Neumann, aidé de Stanislaw Ulam, qui cherchait à concevoir une machine abstraite capable de se reproduire elle-même, à la manière des êtres vivants. L’idée gagna une immense popularité dans les années 1970 grâce au mathématicien John Conway et à son jeu de la vie, un automate cellulaire aux règles minimales où des configurations de cellules semblent naître, se déplacer, se heurter et parfois se perpétuer indéfiniment. Plus tard, Stephen Wolfram entreprit une étude systématique des automates cellulaires les plus simples et défendit l’idée qu’ils constituent une clé pour comprendre comment la complexité surgit dans la nature. On démontra d’ailleurs que certains automates cellulaires atteignent la pleine puissance d’une machine de Turing et peuvent donc, en principe, tout calculer.
L’intérêt des automates cellulaires est à la fois scientifique et pratique. Ils servent de modèles pour simuler quantité de phénomènes naturels où de nombreux éléments semblables interagissent localement: propagation d’un incendie ou d’une épidémie, écoulement d’un fluide, croissance de cristaux, motifs sur la robe de certains animaux, dynamique du trafic routier. Leur structure très régulière se prête particulièrement bien au calcul massivement parallèle, où de nombreuses opérations s’effectuent simultanément. Au-delà de leurs usages concrets, ils offrent surtout une leçon conceptuelle profonde et durable: ils montrent de façon éclatante que des règles élémentaires appliquées localement suffisent à engendrer une complexité globale imprévisible, idée qui résonne bien au-delà de l’informatique, jusqu’en physique, en biologie et dans l’étude des systèmes complexes.
Laisser un commentaire