Les automates cellulaires élémentaires

Wolfram règle 110Le monde du vivant tel qu’on le connait est d’une fantastique complexité; et pourtant à la base, il n’est fait que d’un nombre assez limité d’éléments chimiques, qui  interagissent selon des lois relativement simples et bien connues. De fait l’apparition de la vie est certainement l’exemple le plus fascinant de cette question que l’on retrouve dans de nombreux domaines de la science :

Comment des objets simples interagissant selon des règles simples, peuvent-ils engendrer des comportements complexes ?

Grâce aux ordinateurs, on peut maintenant étudier cette question au moyen de programmes informatiques. Et de manière étonnante, pas besoin d’une énorme puissance de calcul : même les simulations les plus simples possibles réservent déjà pas mal de surprises. C’est le cas de ce qu’on appelle les automates cellulaires élémentaires.

Fabriquons un automate cellulaire

Pour réaliser un automate cellulaire élémentaire, nous allons considérer des cases disposées en ligne. Chaque case peut être soit blanche, soit noire. Au démarrage de notre simulation, nous allons supposer qu’une seule case est noire, comme sur le schéma ci-dessous.

ligne_cases_400

Puis nous allons faire évoluer notre système, en définissant des règles qui vont conditionner comment la couleur des cases change à chaque étape de la simulation. Pour faire au plus simple, nous allons supposer que la nouvelle couleur d’une case dépend de sa couleur actuelle et de celle de ses voisines. Voici une règle de ce genre :

  • si une case est noire, elle reste noire.
  • si elle est blanche, elle devient noire si elle possède au moins une voisine noire.

On peut facilement représenter cette règle graphiquement, car il n’existe que 8 cas à considérer :

automate cellulaire wolfram regle 254

Si on applique cette règle à notre situation de départ avec une seule case noire, voici ce que l’on obtient à chaque pas de temps :

evol_detail_254_400

Pour représenter l’évolution d’un automate cellulaire élémentaire, on peut le simuler sur plusieurs centaines d’itérations, et superposer les différentes lignes obtenues. Dans le cas ci-dessous, on obtient un dessin comme celui ci-dessous.

rule_254_299_px

Rien de bien étonnant vous allez me dire. Vous avez raison ! Alors modifions un peu les règles qui régissent notre automate et voyons ce qui se passe.

Toutes ces investigations ont été réalisée dans les années 1980 par le physicien Steven Wolfram. Pour une raison que j’expliquerai plus bas, il a donné à chacune des règles possibles un petit numéro qui l’identifie : la règle ci-dessus s’appelle la règle 254. Voici ci-dessous quelques exemples des règles considérées par Wolfram.

Un peu de variété

Partons de la règle précédente, et modifions une seule chose : dans la nouvelle règle, si une case noire est entourée par deux cases blanches, elle devient blanche. Dans ce cas j’obtiens la règle dite « numéro 250 », qui est représentée ci-dessous à gauche (j’ai souligné en rouge le changement). Le dessin de son évolution est assez semblable au précédent, c’est un triangle, mais cette fois j’obtiens à l’intérieur une sorte de damier. Je peux également faire une autre modification simple de la règle précédente (voir ci-dessous à droite) et obtenir un autre type de structure périodique, avec des bandes blanches et noires alternées (il s’agit de la règle 50).

rule_250_and_190_600px

Encore une fois, rien de bien excitant. Je pars d’une situation simple qui est une unique case noire. J’applique des règles simples de transformation, les mêmes pour toutes les cellules. Et j’obtiens un dessin très régulier. Normal, non ?

Eh bien maintenant considérons une nouvelle règle. Elle est quasiment identique à la première que nous avons considérée, avec une seule différence : si une case noire est entourée par deux cases également noires, elle devient blanche au tour suivant. Cette règle est appelée règle 126, et voici ce qu’elle donne :

regle_rule_126_400

Bizarre, non ? On reconnait une structure fractale connue sous le nom de triangle de Sierpinksi. Voilà qui est bien différent de nos structures régulières précédentes ! N’est-ce pas fascinant que des règles locales élémentaires aussi simples puissent engendrer une organisation globale aussi complexe que cette figure ? Mais ça n’est pas tout.

Un peu de chaos

Parmi les règles considérées par Stephen Wolfram, l’une possède une évolution tout-à-fait étonnante : il s’agit de la règle numéro 30. Elle est représentée ci-dessous :

regle30_400

rule_30_599_px

Si on regarde seulement le début de l’évolution, on a l’impression que cet automate dessine des structures régulières. C’est également le cas sur la partie gauche du dessin. Mais sur la partie droite, des structures en triangle de différentes tailles apparaissent et disparaissent sans logique apparente. En fait, Wolfram a montré que cet automate avait un comportement totalement désordonné et même chaotique. Son évolution semble totalement aléatoire, et pourtant encore une fois il est défini par des règles simples et une situation de départ simple. Encore une surprise des automates cellulaires élémentaires : des règles simples et déterministes peuvent engendrer le chaos !

Un peu d’émergence

Dans la classification réalisée par Wolfram, un autre automate possède un statut à part encore plus incroyable : il s’agit du numéro 110. Il ne diffère de la règle 126 (celle des fractales) que par un seul changement (souligné en rouge ci-dessous). Si l’on étudie son évolution (en prenant toujours une case noire comme point de départ), on s’aperçoit qu’il reste totalement blanc sur la droite. En revanche sur la gauche, il se passe des choses étranges. En voici la règle ainsi que les 600 premières itérations, je n’ai représenté que la partie gauche.

regle110_400

rule_110_1199_px_crop

A première vue, le motif a l’air franchement régulier, et ce quasiment partout. Mais quand on y regarde de près, on voit que sur ce motif régulier apparaissent et disparaissent des structures étranges : des séries de triangles blanc qui se propagent, ainsi que des bandes noires diagonales. Toutes ces structures semblent interagir : elles apparaissent, se rencontrent, disparaissent; le tout sur ce paysage de fond très régulier.

Je n’ai évidemment pas la place de représenter plus loin l’évolution de cet automate, mais Stephen Wolfram l’a simulé très loin, et aussi loin que l’on aille, ce comportement bizarre demeure. L’automate cellulaire 110 est l’exemple le plus simple que l’on connaisse de comportement complexe émergeant de règles élémentaires toutes simples. Une sorte d’analogue de vie artificielle en miniature !

La règle 110 est sans conteste la plus fascinante de toutes les règles étudiées par Wolfram, mais son cas n’est pas unique. Les automates cellulaires élémentaires que nous avons rencontré ici fascinent par leur simplicité, mais il est possible d’obtenir des choses analogues avec des systèmes à peine plus compliqués. L’un de ces systèmes est ce qu’on appelle (un peu improprement) le jeu de la vie (voir ce billet de Dr Goulu), et sur lequel il faudra que je fasse un billet un jour !

Un autre encore plus fascinant à mon goût est la fourmi de Langton, sur laquelle j’ai déjà écrit un billet que je vous invite à aller lire. Et pour la route, voici une petite simulation de la Fourmi que j’avais réalisée à l’époque


Pour aller plus loin

Si vous vous demandez d’où vient la numérotation de Wolfram, l’idée est très simple. Comme je l’ai montré, pour définir complètement une règle, il n’y a que 8 situations à considérer. Il n’y a donc que 2^8=256 règles possibles. Le numéro qu’on attribue à chaque règle est simplement la représentation en binaire de sa définition par des cases noires et blanches.

règle 110 wolframEn fait, on constate rapidement que parmi les 256 règles, beaucoup sont identiques par une symétrie droite/gauche, ou une symétrie noir/blanc. Il n’existe en réalité que 88 règles non-équivalentes. Un point que je n’ai pas développé, c’est qu’on peut parfaitement appliquer ces règles à une situation initiale qui est autre chose qu’une unique case noire. Les propriétés d’émergence de comportement chaotiques ou complexes sont évidemment plus spectaculaires quand on ne part que d’une seule case noire, mais on peut très bien s’amuser à partir d’une situation initiale aléatoire, comme sur le dessin ci-contre, qui représente la règle 110 évoluée à partir d’une ligne initiale tirée au hasard (conditions aux limites périodiques !)

Tous les schémas de ce billet ont été faits en Python. Mais simuler un automate cellulaire élémentaire est assez trivial, donc laissé en exercice au lecteur !

Dernière précision sur la règle 110 : Wolfram avait depuis longtemps conjecturé que cette règle était universelle. Cela signifie grossièrement que n’importe quel calcul ou programme informatique peut être simulé à partir de cette règle. La preuve de ce résultat a été apportée par Matthew Cook and Steven Wolfram en 2002.

Stephen_Wolfram_PRPour finir un petit mot sur le personnage de Wolfram, que je vous invite à découvrir si vous ne le connaissez pas : il commence la physique des particules à 12 ans, entre 16 et 20 ans, il publie 16 articles dans des revues internationales majeures. Il soutient sa thèse à Caltech à 20 ans. Puis quelques années plus tard il change complètement de domaine et commence à étudier les automates cellulaires élémentaires. Quelques années plus tard, nouveau changement : il quitte le système académique et fonde Mathematica, le célèbre logiciel de manipulation symbolique. Il devient évidemment très riche, puis entre 1992 et 2002, il travaille à nouveau sur les automates cellulaires et en 2002 publie un pavé sobrement intitulé A New Kind of Science, qui prétend plus ou moins relier tous les domaines de la science aux automates cellulaires.

En 2009, sa société annonce le lancement de Wolfram Alpha, un moteur « de réponses », auquel on peut poser des questions dont il va chercher à calculer la réponse. Assez fascinant ! La technologie n’est peut être pas totalement mûre, mais certainement prometteuse.

Alors oui, le type est prétentieux et mégalo, mais c’est quand même un putain de génie.

17 réflexions sur “Les automates cellulaires élémentaires

  1. Pingback: Les automates cellulaires élément...

  2. Vous avez dit:

    «  »On reconnait une structure fractale connue sous le nom de triangle de Sierpinksi. Voilà qui est bien différent de nos structures régulières précédentes ! N’est-ce pas fascinant que des règles locales élémentaires aussi simples puissent engendrer une organisation globale aussi complexe que cette figure ? «  »

    Le triangle de Sierpinski est bien simple.Vous confondez probablement régularité fractale avec complexité.Il peut ètre généré très facilement avec les régles de LIndemayer (Les programmes pour enfant avec une tortue).
    Voici une variation du triangle de Sierpinski que j´ai dessiné avec les règles deLindemayer (sur un programme écrit en Java; mais pas par moi).
    Il est généré tout simplement par : F-F-F-FF-F-F-F (ou F est une translation de longueur = le côté du triangle et – est une rotation de 120 degrés dans le sens inverse des aiguilles d´une montre)
    Remarquez que le triangle de Sierpinski est matriciellement un triangle de 2X2 alors que le mien est un triangle matriciellement de 3×3.

    Voici ma page web sur ces fractals simples; en espagnol:

    http://lit-et-raire.blogspot.com.es/2012/06/fractales-simples.html

  3. Je ne m´étais jamais penché sur ces automates ¿ »cellulaires »? (que veut dire cellulaire dans ce contexte ; est-ce que cela a quelque chose à voir avec la cellule?) quoique je connais l´excellence programmative de Wolfram et la bonne divulgation mathématique sur Internet de son Mathworld.
    Il serait intéresant de savoir s´il y avait un règle qui générait mon fractal triangulaire de 3×3. Et aussi si l´on peut **savoir d´avance** quelles sont les règles qui vont produire des fractals et celles qui n´en produiront pas. Je pense que mon triangle fractal triangulaire de 3×3 pourra être produit, s´il ne l´est pas par l´une des 256 règles; par une extention à 4 cases (au lieu de 3) et dans ce cas il y aurait 2^(2^4) = 2^16 = 65536 règles diffèrentes possibles. Mais je n´ai pas étudié la question; ces automates son nouvaux pour moi.

  4. Pingback: Les automates cellulaires élément...

  5. La fractale la plus connue de Mandelbrot consiste en une élevation au carré d´un nombre complexe plus une constante, ce qui n´est pas simple à représenter avec des opérations géometriquement simples comme la simple translation et la simple rotation ou bien par le systhème de coloration binaire (noir/blanc) de cases adyacentes de Wolfram. Mais il serait intéressant d´essayer de rendre ces fractales de Mandelbrot ou du plus oublié Julia ;géométriquement simples.

  6. Le triangle fractal de Sierpinski est formé par F-F-F-FF-F-F-F ; (matriciellement un 2×2) avec un angle de 120 degrés.

    Un triangle fractal de 3×3 (matriciellement) est formé par F-F-F-FF-F-F-F-FF-F-F-F .

    L´image c´est un triangle fractal de 5×5, matriciellement. Il manque une couche intérieure de triangles:(Sierpinski c´est un 2×2)

  7. Ceci est un triangle fractal de 5×5 complet (avec sa couche intérieure: ses deux couches de triangles fractalisés) dans sa troisième iteration.

    Le code pour le produire sur un programme qui utilise les règles iteratives de Lindemayer, est:

    F-F-F-FF-F-F-FF-FF-F-F+F-FF-F-F-FF-F-F-F

    angle de roattion de 120 º dans le sens inverse des aiguilles de la montre.

  8. Pingback: Les automates cellulaires élément...

  9. Pingback: C’est pas plus compliqué que cela ! | Grorico's corner

  10. Avec votre deuxième règle, si une case noire est entourée par deux cases blanches elle devient blanche. On a à t0 : Blanc – Noir – Blanc. On a obtient donc à t1 : Blanc – Blanc – Blanc qui reste comme cela tout le temps, on a donc pas de triangle. Pourriez-vous m’expliquer ce que je n’ai pas compris ?

    • Attention,la règle ne définit que ce qui arrive pour la case du milieu des trois ! Si on a blanc-noir-blanc, alors la case du milieu (la noire) devient blanche. Par contre les deux autres (celles qui sont de part et d’autre, et sont blanches) deviennent noire d’apres les cas 4 et 7 de la règle.

  11. Pingback: Petite revue des thèmes de TPE qui peuvent nous inspirer… – Faire des Maths… autrement

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s