Le « jeu de la vie » des mathématiques révèle des modèles répétitifs recherchés depuis longtemps | Magazine Quanta

En 1969, le mathématicien britannique John Conway a conçu un ensemble de règles d’une simplicité séduisante permettant de créer des comportements complexes. Son Jeu de la Vie, souvent appelé simplement Vie, se déroule sur une grille carrée infinie de cellules. Chaque cellule peut être « vivante » ou « morte ». La grille évolue au fil d'une série de tours (ou « générations »), le sort de chaque cellule étant déterminé par les huit cellules qui l'entourent. Les règles sont les suivantes:

1. Naissance : Une cellule morte avec exactement trois voisines vivantes devient vivante.
2. Survie : Une cellule vivante avec deux ou trois voisins vivants reste en vie.
3. Mort : Une cellule vivante avec moins de deux ou plus de trois voisins vivants meurt.

Ces règles simples créent un éventail étonnamment diversifié de modèles, ou « formes de vie », qui évoluent à partir des nombreuses configurations de départ possibles de la grille. Les amateurs du jeu ont recensé et taxonomisé ces modèles de manière toujours plus vaste. catalogue en ligne. Conway a découvert un modèle appelé clignotant, qui oscille entre deux états.

L’année suivante, il a découvert un modèle beaucoup plus complexe appelé pulsar, qui oscille entre trois états différents.

Peu de temps après la découverte des oscillateurs, les premiers explorateurs du jeu se sont demandés s’il existait des oscillateurs pour chaque période. "Au début, nous n'avons vu que les périodes 1, 2, 3, 4 et 15", a déclaré le programmeur informatique et mathématicien Bill Gosper, qui découvrira 17 nouveaux oscillateurs différents au cours des décennies suivantes. Les oscillateurs de la période 15 (illustrés ci-dessous) sont apparus étonnamment souvent lors de recherches aléatoires.

Des surprises attendaient ceux qui voulaient les trouver. "D'après les heures et les jours de visionnage, la période 5 semblait impossible", a déclaré Gosper. Puis, en 1971, deux ans après l’invention du jeu, on en trouva un. La recherche de nouveaux oscillateurs est devenue un objectif majeur du jeu, une quête renforcée par l'avènement de la technologie informatique. Les récits de recherches secrètes menées sur des ordinateurs de bureau sont devenus la pierre angulaire du folklore du jeu. « La quantité de temps informatique volée aux ordinateurs centraux des entreprises et des universités était stupéfiante », a déclaré Gosper.

Tout au long des années 1970, les mathématiciens et les amateurs ont occupé les autres périodes courtes et en ont découvert quelques-unes plus longues. Finalement, les mathématiciens ont découvert une manière systématique de construire des oscillateurs à longue période. Mais les oscillateurs avec des périodes comprises entre 15 et 43 se sont avérés difficiles à trouver. « Cela fait des années que les gens essaient de trouver un juste milieu », a déclaré Maïa Karpovitch, étudiant diplômé à l'Université du Maryland. Combler les lacunes a obligé les chercheurs à imaginer une série de nouvelles techniques qui ont repoussé les limites de ce que l'on pensait possible avec les automates cellulaires, comme les mathématiciens appellent les grilles évolutives comme la vie.

Karpovich et six co-auteurs ont maintenant annoncé dans un Prépublication de décembre qu'ils ont trouvé les deux dernières périodes manquantes : 19 et 41. Une fois ces lacunes comblées, la vie est maintenant connue pour être « omnipériodique » – nommez un entier positif, et il existe un modèle qui se répète après autant d'étapes.

La communauté naissante consacrée à l’étude de la vie, qui comprend de nombreux mathématiciens chercheurs mais aussi de nombreux amateurs, a découvert non seulement des oscillateurs mais aussi toutes sortes de nouveaux modèles. Ils ont trouvé des modèles qui voyagent à travers la grille, appelés vaisseaux spatiaux, et des modèles qui construisent d'autres modèles : des armes à feu, des constructeurs et des reproducteurs. Ils ont trouvé des modèles permettant de calculer des nombres premiers, et même des modèles capables d’exécuter des algorithmes arbitrairement compliqués.

Les oscillateurs avec des périodes inférieures à 15 peuvent être trouvés manuellement ou avec des algorithmes rudimentaires qui recherchent les oscillateurs une cellule à la fois. Mais à mesure que la période s'allonge, la complexité augmente également, ce qui rend les recherches par force brute beaucoup moins efficaces. "Pour de petites périodes, vous pouvez effectuer une recherche directement", a déclaré Matthias Merzenich, co-auteur du nouvel article qui a découvert le premier oscillateur de période 31 en 2010. "Mais vous ne pouvez pas vraiment aller au-delà. Vous ne pouvez pas simplement choisir une période et la rechercher. (Merzenich a obtenu son doctorat en mathématiques à l'Oregon State University en 2021, mais travaille actuellement dans une ferme.)

En 1996, David Buckingham, consultant informatique indépendant canadien et passionné de la vie qui recherchait des modèles depuis la fin des années 1970, a montré qu'il était possible de construire des oscillateurs de période 61 et plus en envoyant un modèle autour d'une piste fermée dans une boucle sans fin. . En contrôlant la longueur de la boucle – et le temps qu’il fallait au modèle pour effectuer un aller-retour – Buckingham a découvert qu’il pouvait rendre la période aussi grande qu’il le souhaitait. "C'est de la chimie sans les drôles d'odeurs ni les verres brisés", a-t-il déclaré. "Comme construire des complexes, puis explorer les interactions entre eux." Cela signifiait que, d’un seul coup, il avait trouvé un moyen de construire des oscillateurs de périodes arbitrairement longues, à condition qu’elles soient supérieures à 61.

De nombreux résultats ont été obtenus au milieu des années 1990, lorsque de nombreux oscillateurs manquants entre 15 et 61 ont été découverts grâce à des combinaisons créatives d'oscillateurs connus, auxquels avaient été attribués une multitude de noms colorés. Les traiteurs se mêlaient aux feux de circulation, les volcans crachaient des étincelles et les mangeurs mangeaient des planeurs.

Au tournant du XXIe siècle, seules une douzaine de périodes étaient encore en suspens. "Il semblait tout à fait possible de résoudre ce problème", a déclaré Merzenich. En 21, une nouvelle découverte appelée boucle Snark a amélioré la technique de Buckingham de 2013 et a abaissé le seuil au-dessus duquel il était facile de construire des oscillateurs de 1996 à 61. Cela n'a laissé que cinq périodes manquantes. Un autre a été découvert en 43 et deux autres en 2019, n’en laissant que 2022 et 19 – tous deux premiers. "Les valeurs premières sont plus difficiles car vous ne pouvez pas utiliser d'oscillateurs à petite période pour les construire", a déclaré Merzenich.

Mitchell Riley, chercheur postdoctoral à l'Université de New York à Abu Dhabi et autre co-auteur du nouvel article, est depuis longtemps intrigué par un type d'oscillateur appelé hassler. "La façon dont fonctionnent les tracassiers est la suivante: vous avez un modèle actif au milieu et des éléments stables à l'extérieur qui réagissent avec lui", a expliqué Riley. L'élément stable, appelé catalyseur, est là pour ramener le modèle actif à son état d'origine.

Les concevoir est difficile. "Tous ces modèles sont incroyablement fragiles", a déclaré Riley. "Si vous déplacez un seul point, il explose généralement."

Riley a créé un programme appelé Barrister pour rechercher de nouveaux catalyseurs. « Ce que nous recherchons, ce sont des natures mortes robustes. Le fait est que nous voulons qu’ils interagissent avec ce qui se passe au milieu, puis récupèrent », a déclaré Riley.

Riley a introduit les catalyseurs que Barrister a trouvés dans un autre programme de recherche qui les a associés à des modèles actifs. Cela a conduit à des échecs, a-t-il déclaré. « Il est assez rare qu’un de ces catalyseurs survive à l’interaction. Il n’y a aucune garantie de succès. Vous croisez simplement les doigts et espérez remporter le jackpot. C’est un peu comme jouer au jeu. »

Finalement, son pari a été récompensé. Après quelques quasi-accidents – et une modification du code qui a élargi la recherche pour inclure des modèles symétriques – il a trouvé une interaction catalytique qui pourrait alimenter un oscillateur de période 19. "Les gens avaient essayé toutes sortes de recherches très compliquées avec beaucoup de catalyseurs et beaucoup de choses actives rares au milieu, mais tout ce qu'il fallait était de trouver ce nouveau gros catalyseur", a déclaré Riley.

La dernière période manquante, 41, a été trouvée par Nicolo Brown, un autre co-auteur, qui étudie toujours en mathématiques à l'Université de Californie à Santa Cruz. Brown a utilisé des planeurs comme catalyseurs, une idée proposée pour la première fois par Merzenich.

"Nous avons découvert tellement de comportements profonds au cours des 10 dernières années", a déclaré Karpovich. « Tout le monde fait la fête pendant une semaine, puis passe à autre chose. Il y a tellement d’autres problèmes à résoudre. Les oscillateurs d’une période donnée peuvent-ils être réduits ? Peut-on trouver des oscillateurs dans lesquels chaque cellule oscille ? Les armes peuvent-elles être fabriquées avec des périodes particulières ? Les vaisseaux spatiaux peuvent-ils être amenés à voyager à des vitesses particulières ?

Comme l’a dit Buckingham : « C’est comme être un enfant dans un magasin de jouets infini ».