Dans le numéro d’Octobre 1970 de Scientific American, Martin Gardner publie un article intitulé « Les combinaisons fantastiques du Jeu de la Vie de John Conway » [Gardner70]. Conway a inventé un automate cellulaire qui a la particularité suivante : des figures peuvent croître et atteindre une grande taille mais pourtant, on ne peut dire de façon évidente s’il existe des figures qui vont croître à l’infini. Cet automate cellulaire se nomme ‘Game of Life’ ou ‘Life’ en abrégé.
Les règles du Jeu de la Vie sont extrêmement simples. Les cellules peuvent se trouver dans deux états qui sont : vivant / mort, l’espace cellulaire est composé de cellules qui se trouvent dans l’état mort au départ, sauf pour un nombre fini d’entre elles. L’évolution de chaque cellule est déterminée en fonction du nombre Nv de cellules vivantes se trouvant dans les huit cases adjacentes à une cellule. Les règles sont :
· Une cellule vivante meurt (devient vide) pour Nv = 1 : cela correspond à un état d’isolement de cellule.
· Une cellule vivante meurt pour Nv = 4 : cela correspond à un état de surpeuplement autour de la cellule.
· Une cellule morte peut devenir vivante pour Nv = 3 : cela correspond à une reproduction « trisexuée ».
Le Jeu de la Vie marque un tournant dans l’étude des automates cellulaires car contrairement aux modèles précédents où l’on décidait des règles et du nombre d’état dans un but bien précis (prouver la calculabilité universelle, la constructibilité universelle), on cherche désormais à trouver les propriétés des automates d’après leur règles de fonctionnement. Le travail des chercheurs s’apparente alors à celui des physiciens qui étudient des phénomènes, préparent des expériences et essaient de découvrir de nouveaux objets. Néanmoins, il existe une différence de taille avec le travail des physiciens : l’évolution des objets manipulés, bien que totalement déterminée par les fonctions de transition, est hautement imprévisible. On remarque ainsi qu’il n’y a pas de correspondance apparente entre la taille d’une configuration initiale et le temps qu’elle met pour se stabiliser. Par ailleurs, le simple fait d’ajouter ou d’enlever une cellule dans une configuration change son évolution de façon radicale. Comment, dans ces conditions, espérer parvenir à construire une expérience ?
L’étude des propriétés de Life a démarré avec celle de la découverte des objets stables. Généralement, les chercheurs classent les objets selon leur forme de stabilité. Les objets les plus simples à étudier sont ceux qui restent identiques à eux-mêmes avec le temps, un bloc carré de quatre cellules par exemple. Viennent ensuite les objets qui dont l’évolution est périodique, nommés oscillateurs. L’oscillateur le plus simple est le ‘clignotant’ ; il est constitué de trois cellules alignées, et possède une période 2. Une autre classe d’objets importants est celle des objets périodiques qui se translatent avec le temps. Le planeur est l’exemple le plus simple et il apparaît de façon spontanée lors des simulations.
Petit à petit, les chercheurs ont procédé comme des naturalistes et ont découvert des figures stables de plus en plus complexes. Ces découvertes se font selon deux méthodes : la première consiste à initialiser l’espace cellulaire de façon aléatoire et à observer les figures qui apparaissent de façon spontanée (cf. ANNEXE B). La seconde méthode consiste à construire, par des procédés souvent très ingénieux, des figures périodiques qui éventuellement se translatent. Un grand concours -implicite - a débuté au début des années 70 pour la découverte de nouvelles figures stables. Les chercheurs ont rivalisé d’astuce et ont fini par mettre à jour toute une faune exotique qui peuple l’univers du Jeu de la Vie. Des noms aussi évocateurs que « le mangeur, la navette, le crapaud, le phare ou le serpent » ont été donnés (et continuent d’être données) aux figures stables découvertes. On peut dresser un parallèle avec ce qui se produit en astronomie, où les chercheurs rivalisent pour l’observation de nouveaux astres, avec à la clé la possibilité de nommer l’astre du nom du découvreur.[12] Vu de l’extérieur, cette course folle au plus complexe semblait futile aux autres scientifiques. L’étude du Jeu de la Vie prit des proportions telles qu’en 1974, on pouvait lire dans les colonnes du magazine américain Time que « des heures de calcul représentant des millions de dollars avaient été gaspillées par la horde grandissante des fanatiques de ce jeu » [Time74].
Ce jugement sévère était-il justifié ? Ces chercheurs étaient-ils des « fanatiques » ou à l’opposé plutôt des « scientifiques » dont la discipline n’était pas encore reconnue ? La recherche des propriétés de Life peut-elle être qualifiée de « scientifique » ? Selon le scénario proposé par Kuhn, une discipline scientifique apporte des « énigmes » [puzzles] à la communauté scientifique concernée. Nous pouvons donc essayer d’estimer la ‘scientificité’ de l’étude du Jeu de la Vie en étudiant les « énigmes » qui sont nées de l’étude du Jeu de la Vie.
Le premier problème fut posé par Conway lui-même qui, en 1970, conjectura qu’il existait des figures (ensembles de cellules vivantes) qui pouvaient croître de façon illimitée. Conway avait créé le Jeu de la Vie en espérant qu’une telle possibilité pourrait être réalisée ; néanmoins aucune preuve mathématique de la réalisation de la croissance illimitée ne pouvait être établie. Il fallait donc exhiber une figure dont l’évolution soit totalement prévisible et dont la taille augmente de façon régulière. Gardner offrit un prix symbolique à celui qui arriverait à prouver ou à réfuter la conjecture de Conway avant la fin de l’année. Le prix fut remporté par William Gosper et cinq autres informaticiens du MIT qui réussirent à exhiber une figure, baptisée lance-planeur (« glider gun »), qui est un oscillateur à l’évolution cyclique et qui a la propriété d’émettre un planeur toute les trente générations. Une telle découverte n’aurait rien d’impressionnant de nos jours mais il faut se souvenir qu’en 1970, nous sommes à l’aube de l’ère informatique et que les simulations d’évolutions se mènent parfois à l’aide de pions de jeu de dames ou d’Othello. L’existence du « lance-planeurs » constituait la première résolution d’une énigme liée au Jeu de la Vie : elle démontrait que la croissance illimitée était possible.
Un autre problème qui a occupé la communauté des chercheurs fut celui de la réversibilité. Un automate est dit être réversible s’il ne se produit pas de perte d’information au cours de l’évolution de l’automate : chaque configuration possède donc un unique successeur (déterminisme de l’AC) et un unique prédécesseur. Il est clair que l’on peut déduire facilement des règles du Jeu de la Vie que l’on n’est pas en présence d’un automate réversible puisque des configurations différentes peuvent avoir un même successeur. Par contre, une propriété qui n’était pas évidente était l’existence de configurations qui n’admettent aucun état qui puisse les engendrer. De telles configurations sont appelées « jardins d’Eden » car elles ne peuvent être que des états initiaux ; on peut donc dire de façon imagée « qu’elles ont tout simplement été crées ». La question du jardin d’Eden est posée pour la première fois par Moore en 1962 [Moore62], concernant les automates auto-reproducteurs. L’existence de jardins d’Eden n’a rien d’évident, car on ne voit pas a priori ce qui empêcherait une configuration donnée d’avoir un prédécesseur. En 1970, le mathématicien Alvy Ray Smith démontra l’existence de jardins d’Eden dans Life, puis un exemple fut donné par Banks. La configuration qu’il propose tient dans un rectangle de 9 par 33 cellules, cf. [Heudin98, p.62], [Poundstone85, p.50], elle est donc relativement complexe ; la démonstration elle-même est assez sophistiquée, ce qui se comprend aisément puisqu’il s’agit de montrer qu’aucune configuration de Life ne peut engendrer le candidat au titre de jardin d’Eden. Le Jeu de la Vie donne donc naissance à des problèmes qui font certes appel à l’informatique mais dont la résolution requiert des techniques purement mathématiques. D’autre part, la découverte de figures stables de plus en plus élaborées semblait montrer que malgré l’impossibilité de prévoir l’évolution de la majorité des configurations, il existait néanmoins un certain ordre dans cet univers.
Jusqu’à quel point pouvait-on maîtriser l’univers de Life ? La question fondamentale était de déterminer si Life possédait les capacités de calculabilité et constructibilité universelle. Nous avons vu (cf. I.1.) que Von Neumann avait prouvé qu’un automate cellulaire pouvait servir de calculateur universel en utilisant un modèle qui employait 29 états élémentaires et dont les « lois de la physique » ne respectaient pas les conditions de symétries élémentaires telles que l’invariance par rotation et l’invariance par réflexion. Codd dans [Codd68] a fait un pas de plus vers la simplification en montrant que la condition de calculabilité universelle pouvait être réalisée par un automate cellulaire à 8 états élémentaires avec un voisinage de cinq cellules (4+1) et des règles qui respectaient l’invariance par rotation mais non l’invariance par réflexion. Jusqu’où pouvait-on continuer dans cette recherche de simplicité ? Était-il possible que Life, qui était bien plus simple dans son nombre d’états et dans ses règles puisse avoir la même puissance de calcul et de construction ? Le mystère restera entier jusqu’en 1982 où Conway publiera, avec d’autres chercheurs, une preuve détaillée de la possibilité de simuler n’importe quel calcul à l’aide du Jeu de la Vie [Berlekamp&al.82].
Dans la construction de Conway, l’unité de base qui sert à la circulation de l’information, l’équivalent d’un bit en théorie de l’information, est le planeur. Chaque nombre peut être codé selon un faisceau de planeurs généré par un lance-planeurs, et on montre que toutes les portes logiques telles que ET, OU, NON ainsi que les propriétés de mémoire en lecture / écriture peuvent être réalisées à l’aide d’interactions entre figures stables connues. Conway a aussi montré que l’on pouvait concevoir un constructeur universel dans le Jeu de la Vie. Le lecteur qui souhaiterait avoir un exposé simplifié mais qui reprend chaque étape de la démonstration de Conway peut se reporter à [Poundstone85, chap. 12]. Les constructions utilisées dans la démonstration pourront sembler étranges, complexes, voire tortueuses aux personnes habituées aux mathématiques « classiques », mais si l’on s’y intéresse en détail on retrouve la même élégance, la même quête de l’essentiel que dans une démonstration de mathématiques. Le Jeu de la Vie allait donc apporter la preuve que la condition de calculabilité universelle peut être réalisée par un automate ayant 2 états, un voisinage de 9 cellules, et aux règles invariantes par rotation et par réflexion. A ce jour, des automates cellulaires réalisant la condition de calculabilité et de constructibilité universelle, Life est l’automate le plus simple que l’on connaisse. La démonstration de Conway allait quasiment clore le chapitre concernant le Jeu de la Vie, en effet la possibilité même de la démonstration semblait indiquer que l’on maîtrisait « suffisamment » la physique de ce monde. Il était donc temps d’explorer de nouveaux mondes.