Les automates cellulaires élémentaires

Le 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.

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 :

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 :

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.

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).

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 :

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 :

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.

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

[youtube=http://www.youtube.com/watch?v=i8N2xnMm6qE]

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.

En 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.

Pour 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.