Les Newsletters Interstices
    Niveau facile
    Niveau 1 : Facile

    À la découverte des automates cellulaires

    Culture & Société
    Algorithmes
    Explorer les relations mathématiques entre les phénomènes observés chez des êtres vivants et des machines, c'est là l'une des possibilités offertes par les automates cellulaires. Découvrez ce moyen d'investigation des processus auto-reproductifs à travers différents exemples d'automates cellulaires...

    Il y a près de soixante ans, profitant des techniques développées durant la seconde guerre mondiale, des scientifiques allaient explorer les relations mathématiques qui existent entre les phénomènes observés chez des êtres vivants et des machines. On commence ainsi à examiner les analogies de comportement entre des radars qui suivent une cible et des animaux cherchant à satisfaire leurs besoins. Dans le même temps, on remarque aussi que la dynamique des suites mathématiques simples ressemble à celle des populations biologiques de par leur caractère fluctuant et imprévisible. Des scientifiques de renom tels Alan Turing ou John von Neumann cherchent également les passerelles permettant de décrire les machines artificielles comme des êtres « vivants ». Tous deux en particulier sont fascinés par les capacités d’auto-reproduction et d’auto-réparation des organismes vivants. Turing propose ainsi un modèle mathématique de la morphogénèse et von Neumann n’hésite pas à poser une question radicale : est-il possible de concevoir une machine capable de s’auto-reproduire ?

    Un automate cellulaire peut être caractérisé par différentes composantes : sa dimension (1, 2, 3, etc.), le voisinage d’une cellule (c’est-à-dire l’ensemble des cellules ayant une influence sur la cellule cible), son espace d’états (le nombre d’états que peut prendre une cellule) et sa fonction de transition (c’est-à-dire que pour un automate à k états, avec un voisinage de r cellules, il peut y avoir r configurations de voisinage différentes).

    L’automate bidimensionnel imaginé par von Neumann assignait 29 états possibles à chaque cellule, avec un voisinage de 5 cellules (cellule cible + 4 voisines adjacentes). Cela apparaît « raisonnable », mais la construction effective de cet automate nécessitait l’initialisation de plus de 200 000 cellules !

    John von Neumann (1903-1957), mathématicien américain d’origine hongroise. Institute for Advanced Study Archives / Photo © Alan Richards

    Tout d’abord pensée en termes techniques, la machine auto-reproductrice de von Neumann est conçue pour puiser des pièces dans un bac de composants simples. Il suffit de monter ces composants ensemble de manière à former une machine identique à elle-même, puis de mettre en marche cette machine-fille. Très vite, ce projet apparaît trop ambitieux et sur une suggestion de son collègue Stanislaw Marcin Ulam (mathématicien américain d’origine polonaise), von Neumann décide alors d’examiner la question dans un espace mathématique simple qui serait une métaphore du monde réel. Cet espace est divisé en une grille pavée de cellules et chaque cellule a un état qui est choisi dans un ensemble fini d’états possibles. L’évolution des états des cellules se fait à temps réguliers : on suppose qu’une horloge donne à chaque pas de temps un signal de mise à jour. Ces changements obéissent à une loi dite locale, c’est-à-dire que chaque cellule met à jour son état en fonction de ce qu’elle « perçoit » de son voisinage. En l’occurrence, dans le modèle de von Neumann, cette perception d’une cellule est limitée à son propre état et à celui des quatre cellules adjacentes (Nord, Sud, Est, Ouest).

    Grâce à son modèle mathématique qu’il appelle d’abord tesselation automata (automate sur pavage) puis cellular automata (automate cellulaire), von Neumann va montrer que l’on peut construire une machine auto-reproductrice tout en garantissant la non-trivialité de cette auto-reproduction. En effet, il démontre que l’univers des automates cellulaires, aussi simple soit-il, permet de simuler le déroulement de toute machine dont le fonctionnement est spécifié sans ambiguïté. Techniquement parlant, il montre que l’on peut inclure dans cet univers une machine de Turing universelle ce qui, moyennant une hypothèse aux fortes implications épistémologiques — il s’agit là de la thèse de Church —, revient à pouvoir simuler le déroulement de n’importe quel algorithme.

    Le Jeu de la vie

    De nos jours, on ne peut toujours pas admirer la construction de von Neumann. Celle-ci est en effet d’une complexité telle qu’une simulation effective du modèle prendrait trop de temps à être réalisée. A contrario, le modèle dit du Jeu de la vie, proposé par le mathématicien britannique John Horton Conway en 1970 est d’une simplicité désarmante. On considère des cellules réparties sur une grille mais celles-ci ont un état binaire : elles sont soit mortes, soit vivantes. La règle de transition locale se décline en deux sous règles, qui dépendent du nombre de voisins vivants parmi les huit cellules adjacentes (Nord, Sud, Est, Ouest ainsi que les cellules diagonales) :

    (a) La règle de naissance stipule qu’une cellule passe de l’état mort à l’état vivant si elle est entourée de trois cellules vivantes.

    La cellule au centre de la grille (en blanc cerclé de rouge) passe de l’état mort (blanc) à celui de vivant (gris) au temps T+1 car elle est entourée de trois cellules vivantes.

    (b) La règle de survie stipule qu’une cellule vivante reste vivante à condition d’être entourée de deux ou trois cellules vivantes, autrement, elle passe à l’état mort.

    La cellule grise au centre de la grille est vivante au temps T et elle le restera au temps T+1 car elle est toujours entourée de deux cellulles vivantes.

    Initialement proposé comme un simple jeu, ce modèle déclencha un fort enthousiasme parmi les premiers aficionados de la programmation : en effet, en dépit de la simplicité des règles, les simulations informatiques permettaient d’observer des phénomènes surprenants dont les traits marquants peuvent se résumer à trois notions intuitives : l’auto-organisation, l’émergence et une évolution imprévisible du système.

    Évolution du modèle du Jeu de la vie sur une grille de 50×50 cellules.
    Les cases blanches et bleues représentent respectivement les cellules à l’état 0 et 1. La configuration initiale est choisie aléatoirement. L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

    L’auto-organisation apparaît lorsqu’on observe l’évolution du Jeu de la vie partant d’un état initial aléatoire où chaque cellule a une chance égale d’être dans l’état vivant ou mort. Au bout de quelques pas de temps, ou pour reprendre la terminologie consacrée, au bout de quelques générations, les simulations montrent que l’état du système a perdu son aspect aléatoire. Il comporte des zones totalement mortes, des îlots stables de cellules vivantes, alors que d’autres restent en évolution.

    Plus surprenante encore est l’apparition des « glisseurs », ces figures qui se déplacent en diagonale à vitesse régulière. Comment se fait-il que de tels déplacements de figures soient possibles alors que les règles ne spécifient aucun comportement de ce type ? Un examen des glisseurs confirme qu’il s’agit presque d’une « coïncidence ». Le glisseur est en fait formé de quatre figures différentes se succédant dans le temps. La quatrième figure est identique à la première, à ceci près qu’elle s’est translatée d’une case ! Cet exemple illustre bien la propriété d’émergence : à un certain niveau d’observation, on voit apparaître des structures dont le comportement n’avait pas été explicitement spécifié au niveau de la règle locale de transition.

    Les glisseurs sont ces figures qui se déplacent en diagonale à vitesse régulière.
    L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

    Évidemment, on pourrait être tenté de décrire le comportement global du système à l’aide d’équations mathématiques. Pour ce faire, on peut chercher à réitérer les observations du système un grand nombre de fois et à dégager des constantes. Mais d’une simulation à l’autre, on observe des gammes de comportement extrêmement variées. Dans le cas de grilles de 50×50 cellules par exemple, le système peut se stabiliser au bout de quelques centaines de générations, tout comme il peut évoluer durant des milliers de générations sans se stabiliser. Un observateur ayant une mémoire infinie et des capacités d’observations infinies, un démon de Laplace informatique en quelque sorte, serait bien sûr à même de prédire l’évolution de n’importe quelle configuration. Malheureusement, pour les observateurs limités que nous sommes, il paraît hors de portée de pouvoir prédire l’évolution du système à l’aide d’équations mathématiques. Cette difficulté à prédire l’évolution du système a d’ailleurs des justifications théoriques : dans le cas d’une grille infinie (cas théorique), on conjecture qu’aucune méthode ne permet de faire plus vite que la simulation.

    D’après le mathématicien, astronome et physicien français Pierre-Simon Laplace, le monde physique est nécessaire car il est entièrement déterminé, c’est-à-dire que l’état présent de l’univers est l’effet de son état antérieur et la cause de son état futur. Le démon de Laplace est un être qu’il a imaginé pour expliquer que si l’Homme ne peut pas tout prévoir, ce n’est pas pour autant que l’univers n’est pas déterministe. Cet être doté d’une intelligence qui connaitraît toutes les forces animant la nature, pourrait en effet prévoir l’avenir.

    Au-delà du Jeu de la vie, la règle de majorité

    Ayant fait la découverte d’un automate cellulaire particulier par le biais du Jeu de la vie, on peut légitimement se demander si cet automate est l’exception ou la règle. Autrement dit, toutes les règles locales produisent-elles des comportements aussi riches ? Pour commencer l’exploration d’autres règles, examinons la règle dite de majorité :

    Évolution du modèle de la majorité sur une grille de 50×50 cellules.
    Les cases blanches et bleues représentent respectivement les cellules à l’état 0 et 1. La configuration initiale est choisie aléatoirement. L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

    Chaque cellule est dans un état binaire et prend l’état majoritairement présent dans son voisinage.

    L’observation du système partant d’un état aléatoire révèle également une forme d’auto-organisation : on voit apparaître des régions uniformes qui ont tendance à devenir de plus en plus homogènes jusqu’à ce que se forment des îlots de cellules blanches dans des « mers » de cellules noires et vice-versa. Ensuite, les contours des « mers » et des « îlots » ont tendance à s’adoucir, c’est-à-dire à devenir plus lisses. À l’inverse du Jeu de la vie, ce processus est rapide : pour des grilles de 50×50 cellules, le système atteint un état stable au bout de quelques dizaines de générations seulement.

    Peut-on là aussi parler d’émergence ? Étant donné que cette propriété n’est pas définie de manière formelle, il est difficile de donner une réponse tranchée. Quant aux possibilités de prédiction de l’évolution du système, elles se trouvent assez limitées dans la mesure où il n’existe pas d’outils propres aux automates cellulaires pour démontrer la règle de majorité. Il est toutefois possible d’utiliser des outils issus de la physique statistique pour démontrer les nombreuses propriétés (mathématiques, statistiques et dynamiques) de cette règle. Néanmoins, même pour un modèle aussi simple, la question de savoir comment prédire efficacement le temps de stabilisation à partir de la condition initiale reste encore non résolue à ce jour.

    Le compteur de parité

    Évolution du modèle du compteur de parité sur une grille de 50×50 cellules.
    Les cases blanches et bleues représentent respectivement les cellules à l’état 0 et 1. La configuration initiale est choisie aléatoirement. L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

    D’autres modèles comme le compteur de parité peuvent également être examinés. Ce modèle présente en effet des propriétés intéressantes. Il attribue aussi un état binaire aux cellules ; une règle stipule qu’au niveau local, chaque cellule compte le nombre de 1 dans son voisinage. Si le nombre total de 1 est pair, la cellule prend l’état 0 sinon, elle prend l’état 1. Là encore, il est difficile de dire a priori ce que donne cette règle lorsqu’on l’applique à une configuration initiale aléatoire. La simulation montre que, contrairement au modèle du Jeu de la vie et à la règle de majorité, le modèle du compteur de parité ne permet d’observer aucune forme d’auto-organisation. Partant d’une configuration aléatoire, le système reste aléatoire sans qu’il soit possible d’observer de stabilisation, même pour des temps de simulation très longs.

    Pour autant, il ne faudrait pas en déduire que le modèle du compteur de parité est sans intérêt. Il illustre la propriété remarquable selon laquelle toute figure initiale s’auto-reproduit. Prenons par exemple la lettre N à l’état initial du système.

    Évolution du modèle du compteur de parité sur une grille de 64×64 cellules.
    La configuration initiale choisie est la lettre N. L’animation ci-dessus a été produite avec le logiciel FiatLux. © Nazim Fatès

    Les simulations montrent que le système évolue de telle sorte que cette lettre N se duplique à l’infini, la seule limitation étant celle de la taille de la grille choisie. Pour se convaincre qu’une telle reproduction a lieu quelle que soit la figure initiale, on peut réitérer l’opération un grand nombre de fois avec des formes différentes, ou tout simplement, faire une analyse mathématique. On confirme ainsi que le système obéit à un principe de superposition et de duplication, ce qui explique pourquoi l’information initiale n’est jamais détruite. Cette propriété montre aussi pourquoi aucun ordre n’apparaît lorsque l’on part d’un état aléatoire : les nouveaux états obtenus sont une superposition d’états aléatoires.

    La morale de l’histoire

    Hormis l’aspect graphique ou ludique, quel est l’intérêt pour un scientifique d’étudier les automates cellulaires ? Les quelques exemples présentés dans cet article ont cherché à convaincre le lecteur qu’en dépit d’un fonctionnement local simple, la richesse de leurs comportements globaux avait de quoi surprendre ! Ceci peut avoir une implication forte sur notre compréhension des systèmes « naturels » : paradoxalement, l’étude des automates cellulaires semble dire que ce n’est pas parce qu’on a une connaissance parfaite des constituants d’un système que l’on comprend nécessairement comment se comporte l’ensemble. De même, l’observation de l’auto-organisation et de l’émergence suggèrent que l’on peut également obtenir des propriétés intéressantes d’un système sans qu’il soit nécessaire d’avoir un contrôle total de ses composants. C’est la raison pour laquelle les scientifiques essaient d’utiliser ces propriétés pour concevoir des systèmes électroniques ou informatiques d’un nouveau type. Les calculateurs actuels nécessitent des techniques de haute précision et ce, pour produire des circuits dans lesquels la position de chaque composant est décidée par avance. Or, les chercheurs pensent qu’en imitant la genèse des organismes vivants, des circuits évolués pourraient se former tout en laissant le système s’organiser avec une certaine autonomie.

    En francais

    En anglais

    • Wikipedia Encyclopedia, Cellular automaton, last modified 9 april 2007.
    • Wikipedia Encyclopedia, Conway’s Game of Life, last modified 7 april 2007.
    • S. Wolfram, A new kind of science, Wolfram Media, 2002.
    • John von Neumann, The theory of self-reproducing automata, A. W. Burks (Ed.), University of Illinois Press, Illinois, 1966.
    • A. Turing, The chemical basis of morphogenesis, Philosophical Transactions of the Royal Society, n°237, 1952.

    Newsletter

    Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Nazim Fatès

    Chercheur Inria dans l'équipe MAIA.
    Voir le profil

    Ces articles peuvent vous intéresser

    ArticleCulture & Société
    Algorithmes

    La riche zoologie des automates cellulaires

    Marianne Delorme
    Jacques Mazoyer

    Niveau intermédiaire
    Niveau 2 : Intermédiaire