| Découvrir | Logiciels & programmation | Liens Web | Propriétés remarquables | Recherche automatisée | Documentation | Zoo |
,
un article publié dans leur numéro de mars 1996 (N°221).
Depuis 25 ans, les biologistes du Jeu de la vie explorent une planète riche et étrange.
John Conway fixa les règles du Jeu de la vie il y a 25 ans et créa une science nouvelle. Depuis, les spécialistes ont poursuivi l’exploration d’un monde dont la définition tient en trois lignes, mais dont la richesse semble inépuisable. La discipline est à la croisée des chemins de la physique – on y construit des machines –, de la biologie – les êtres qu’on y étudie sont des cellules qui naissent et meurent –, des mathématiques – on y prouve parfois des théorèmes – et de l’informatique – les ordinateurs y jouent le rôle de microscopes. Ces cinq dernières années, une bande de passionnés du jeu a beaucoup fait progresser la discipline. Le monde du Jeu de la vie est un plan infini quadrillé dont chaque case est, soit occupée par une cellule, soit vide. Chaque case possède huit voisines et, d’une génération à l’autre, des naissances et des décès s’y déroulent mécaniquement selon la règle simplisme de Conway : si une case est vide et que trois de ses voisines sont occupées, alors une naissance s’y produit (étrange sexualité!) ; si une case est occupée, la survie n’y est possible que si deux ou trois cases voisines sont occupées ; dans tous les autres cas, la case se retrouve vide à la génération suivante. En résumé, naissance si 3 voisins, survie si 2 ou 3 voisins.
Ces règles, choisies parce qu’elles sont assez naturelles (la vie nécessite déjà de la vie, mais trop de vie provoque l’étouffement) et qu’elles engendrent un monde inattendu, ont dépassé toutes les espérances de son créateur. Toutefois les mathématiciens, qui savent traiter des problèmes d’une abstraction et d’une difficulté étourdissante, sont assez démunis pour résoudre la plupart des problèmes que pose cette biologie : lorsqu’ils les résolvent, c’est d’une façon peu satisfaisante, comme nous allons le voir. Cet incapacité laisse le champ ouvert aux étranges ingénieurs-biologistes à qui l’on doit les progrès récents que nous allons présenter.
 |
 |
 |
| Objets stables à 4, 5 et 6 cellules
(fichier au format LIF) |
Objet de période 2
(fichier au format LIF) |
Objets de période 3
(fichier au format LIF) |
Après avoir constaté que certaines figures (configurations de cellules) sont stables, que d’autres sont périodiques (on en connaît des centaines maintenant), diverses questions se posent. La première est : une population de cellules peut-elle croître indéfiniment?
La réponse, positive, a été donnée dès 1970 par des étudiants du MIT; cependant de nouvelles démonstrations plus simples de ce résultat sont disponibles et la figure 2 en indique deux tout à fait amusantes trouvées en 1992 et 1993 : l’Extenseur et le Chasse-neige. à chaque fois, ces configurations avancent en laissant derrière elles une traînée. Cette traînée, stable pour le Chasse-neige, est en mouvement périodique pour l’Extenseur. Si vous placez un obstacle sur le chemin de ces configurations, ne serait-ce qu’un bloc de quatre cellules formant un carré (c’est la configuration stable la plus simple), sa rencontre avec le Chasse-neige ou la tête de l’Extenseur détruira celui-ci, ainsi que toute la traînée qui s’embrase à toute vitesse, laissant, après s’être consumée, des débris éparpillés.
génération 0 |
génération 0 |
génération 100 |
génération 50 |
génération 200 |
génération 100 |
| L'extenseur
fichier LIF |
Le Chasse neige
fichier LIF |
– Peut-on créer une configuration dont le nombre de cellules augmente plus vite que le temps?
 |
 |
|
|
|
Configuration oscillante de période 2 dont on peut faire des variantes aussi grandes qu’on le souhaite et dont le centre recouvre le plan avec une densité 1/2.
 |
 |
|
|
Autres merveilles, les configurations dents de scie, qui sont conçues d’une façon telle que le nombre de cellules augmente puis diminue, puis augmente puis diminue, etc., les maxima atteints étant de plus en plus grands (les effectifs constituent ce que les mathématiciens appellent une suite n’ayant pas de limite). La plus simple des configurations dents de scie connue – qui n’est pas si simple que cela! – est représentée à la figure 4, et son subtil fonctionnement y est décrit.
Cette configuration possède un effectif en dents de scie, c’est-à-dire qui passe alternativement par un maximum (de plus en plus grand), puis par un minimum (constant de 977 cellules). La configuration est composée d’un lance-navires (à gauche) et d’un puffeur qui s’éloigne à droite. Le puffeur laisse derrière lui une traînée de clignotants (un clignotant est un groupe de trois cellules alignées côte à côte). Le lance-navires envoie une salve (unique) de deux navires qui cogne la traînée et en provoque la destruction progressive à la vitesse 2c/3. Lorsque la traînée est détruite (on a alors atteint l’effectif minimum), le puffeur se remet à produire une traînée et envoie un navire en arrière, qui atteint au bout d’un certain temps le lance-navires(qui était resté en quelque sorte en attente sans rien lancer). Celui-ci envoie alors une nouvelle salve de navires qui provoque, quand elle l’atteint, la destruction de la traînée devenue très longue, etc.
| génération 0 |  |
| génération 100 |  |
| génération 200 |  |
| génération 400 |  |
La configuration de Corderman est ce qu’on appelle un puffeur, c’est-à-dire une configuration qui se déplace en laissant derrière elle des débris qui ici forment une sorte de grand zigzag composé de blocs carrés stables (voir la figure 5). Lorsque les traces sont régulières (comme c’est le cas pour l’Extenseur et le Chasse-neige, qui sont aussi des puffeurs), on peut essayer de modifier le puffeur de façon à ce que les débris soient détruits. Le puffeur devient alors un navire : une configuration qui se déplace.
Inversement, à partir d’un navire, on peut souvent construire des puffeurs. La configuration de Corderman semblait donc pouvoir donner naissance à des navires. Mais c’est seulement en avril 1991 que Dean Hickerson réussit cette transformation que les passionnés avaient tentée sans succès pendant de nombreuses années. La transformation en navire n’est en rien évidente, puisque le résultat comporte maintenant 180 cellules, mais le travail en valait la peine, car le navire obtenu est d’un genre inconnu jusqu’alors.
Le puffeur de Corderman est la plus petite configuration
dont on est certain que l’effectif augmente indéfiniment.
(fichier au format
LIF)
Le navire de Corderman a été tiré
du puffeur de Corderman ; contrairement à tous les navires connus
jusqu’en 1989, sa vitesse c/12 est différente de c/2 et de c/4.
(fichier au format
LIF)
L’étude théorique montre qu’un navire de type A– B a nécessairement une période N plus grande que 2(A + B). Par exemple, un navire qui se déplace horizontalement d’une case à la fois ne peut pas le faire en moins de deux générations, et un navire qui se déplace d’une case en diagonale (type 1 – 1) ne peut pas le faire en moins de quatre générations.
Les navires connus il y a dix ans avaient tous une période N multiple de 4 et avaient tous la vitesse c /2 (pour les navires transversaux) ou c /4 (pour les navires diagonaux). La vitesse de la lumière c correspond à un déplacement d’une case par génération horizontalement, verticalement ou en diagonale : rien dans le plan de Conway ne peut se déplacer plus vite que c. Il n’y a aucune raison pour que tous les navires aient les vitesses c /2 ou c /4 et des périodes multiples de 4, et c’est sur ce point que de nombreuses découvertes ont été faites ces dernières années, dont le navire construit par Dan Hickerson qui a une vitesse c /12 et une période de 96. Après 20 ans de chasses infructueuses, il est étonnant qu’on ait pu en quelques années trouver tant de choses nouvelles concernant les navires du Jeu de la vie, au point d’ailleurs que David Bell leur a consacré un livre. Ce sont d’ailleurs les nouveaux navires qui ont conduit au merveilleux Recouvreur-du-plan.
Parmi les découvertes récentes concernant les navires, citons : des navires de période 2 (le premier fut trouvé en 1989 par Dan Hickerson), de période 3 (certains avancent à vitesse c/2, d’autres à la vitesse c/3), de période 5 (certains avancent à la vitesse c/5, d’autres à la vitesse 2c/5). Des grammaires de composants ont été élaborées, qui permettent de construire des bateaux aussi longs ou larges qu’on veut, et des astuces ont été mises au point pour obtenir des bateaux de période aussi grande qu’on le souhaite.
Les méthodes utilisées pour obtenir ces résultats méritent quelques commentaires, car il serait naïf de croire qu’il suffit d’essayer au hasard en écrivant des programmes de quelques lignes. L’exploration àl’aide de programmes est bien un outil essentiel pour ces découvertes, mais c’est à l’aide d’algorithmes subtils qu’on progresse. Ces algorithmes que les passionnés s’échangent entre eux et ajustent année après année, entre autres choses, analysent les essais infructueux déjà tentés pour ne pas rechercher dans des directions peu prometteuses, et essaient des configurations ressemblant à des configurations déjà connues pour être intéressantes.
Le nombre de configurations à explorer est bien trop grand pour que même les plus rapides des ordinateurs puissent découvrir des objets intéressants en procédant bêtement au hasard :le nombre de configurations différentes possibles contenues par exemple dans un carré de 10 cases sur 10 cases est de 2^100 ~ 10^30, ce qui est bien plus que ce qu’ils pourraient explorer même si on confiait aux passionnés du jeu tous les ordinateurs de la terre pendant un an.
C’est donc en perfectionnant programmes et algorithmes, en y intégrant des configurations déjà trouvées, en décomposant les figures intéressantes connues et en les recomposant différemment, bref c’est en utilisant toute l'ingéniosité dont un informaticien peut être capable que les ingénieurs-biologistes du Jeu de la vie trouvent ces machines étranges adaptées à la physique simplifiée du monde de Conway (n ’oubliez pas que tout est toujours régi uniquement par "naissance si 3 voisins ; survie si 2 ou 3 voisins"). Peut-être que du génie est parfois utile.
Un glisseur est une configuration de cinq cellules (voir la figure 2) qui se déplace en quatre générations d’une case en diagonale (c’est le plus simple des navires et sa vitesse est c/4). Les lance-glisseurs sont des configurations qui restent fixées à un endroit, mais qui périodiquement engendrent un ou plusieurs glisseurs qui constituent alors des "courants" de glisseurs et s’éloignent indéfiniment du lance-glisseurs.
Il existe aussi des lance-navires et des puffeurs lance-glisseurs ou lance-navires, et ce sont toutes ces configurations dynamiques qui constituent les composants élémentaires qu’on assemble pour construire les objets ayant un taux de croissance "en log(t)" ou autre.
Il existe, par exemple, des lance-glisseurs qui émettent un glisseur toutes les 30 générations (le premier découvert est de cette catégorie), d’autres toutes les 23 générations. Il en existe aussi de plus compliqués qui émettent toutes les 15 générations (celui-là est assez gros). D’autres émettent un courant irrégulier, car résultant d’une interaction complexe et difficile à analyser ; on les appelle lance-glisseurs aléatoires. D’autres émettent très rarement, par exemple toutes les 360 générations ou plus rarement encore.
La configuration la plus extraordinaire que j’ai vue est construite à partir de navires lance-glisseurs et de navires lance-navires. Elle synthétise une suite de navires exactement espacés comme la suite des nombres premiers : il y a un navire pour 2, un pour 3, un trou pour 4, un navire pour 5, un trou pour 6, un navire pour 7, des trous pour 8, 9, 10, etc. Ce calcul des nombres premiers par une machine du Jeu de la vie était prévu par la théorie.
En effet, en analysant certains des composants disponibles, dès les années 1970, John Conway a réalisé qu’on pouvait créer des courants de glisseurs et les faire interagir entre eux pour obtenir des portes logiques et,ou, non, comme dans un circuit électronique. Les éléments de base pour construire un ordinateur universel(c’est-à-dire capable de calculer toute fonction calculable) étaient donc présents et on en a déduit alors qu’en s’y prenant bien il était possible de faire calculer les nombres premiers à une configuration, ou les coefficients du binôme ou tout ce qui vous intéresse et qu’un ordinateur sait calculer.
| génération 0 |  |
| génération 50 |  |
| génération 100 |  |
| génération 150 |  |
On a là un exemple de la différence entre l’existence mathématique et l’existence pratique. Le mathématicien, même lorsqu’il donne explicitement les règles qu’il faut employer pour obtenir tel ou tel objet (c’est ici le cas), ne se préoccupe pas nécessairement de mener le travail jusqu’à son terme : il sait que c’est possible, il a des arguments abstraits qui l’en persuadent et ça lui suffit. Aux ingénieurs de terminer le travail si Ťa les amuse!
De la même façon, les mathématiciens du Jeu de la vie ont établi depuis longtemps qu’il était possible de construire des navires de type A – B avec A et B quelconques. Pourtant, ainsi que nous l’avons déjà dit, on n’en connaît aujourd’hui que de type A – B avec A = 0 (déplacement vertical) ou B = 0 (déplacement horizontal) ou A = ± B (déplacement diagonal), et donc en particulier aucun navire de type 1 – 2 n’a jamais été vu. Un lecteur saura-t-il en découvrir un?
De même encore, on sait prouver mathématiquement qu’il existe des configurations autoréplicatrices – qui se dédoublent au bout d’un certain nombre de générations –, mais jamais personne jusqu’à présent n’en a aperçu sur son écran d’ordinateur. On le voit, les bâtisseurs d’empires imaginaires que sont les ingénieurs-biologistes du Jeu de la vie ont encore du travail devant eux.
Les gens qui s’occupent du Jeu de la vie sont parfois l’objet de railleries : pour mener toutes ces expériences de biologie imaginaire, ne faut-il pas être fou et irresponsable (car bien sûr les ordinateurs utilisés sont coûteux, et le temps passé à ces recherches pourrait l’être à des calculs plus productifs).
Mais après tout... est-ce si fou que cela d’étudier l’un des plus simples mondes possibles? N’est-ce pas le seul moyen pour évaluer ce qui est nécessaire, comme concepts, comme mécanismes de base, comme chimie minimum, pour faire "fonctionner un monde". Ce que nous voyons se produire dans le plan de Conway nous apprend que, même si notre Univers nous apparaît complexe, cela n'entraîne pas que ses lois le sont.
Le principe du rasoir d'Occam veut qu’on minimise ce qu’on fait intervenir dans une explication ou un modèle : cette exploration du minimum générant la complexité qu’est l’étude du Jeu de la vie peut donc être vue comme une physique ultra-fondamentale ou une biologie théorique ultime. C’est donc un travail scientifique aussi important que bien d’autres menés ici ou là dans les milliers de sous-disciplines scientifiques existant maintenant et qui ne sont pas toujours aussi amusantes et esthétiques!
Jean-Paul Delahaye est professeur d’informatique à l’Université des sciences et techniques de Lille et chercheur au laboratoire d’informatique fondamentale de Lille du CNRS.