Accueilretour
précédentsuivant

Machines arithmétiques

Origines

"Blinkers"

Jardins d'Éden

Navires

Canons...

"Breeders"

Machines

  Premières...

  ... universelles

Métacellules

Documents

 Dès 1970, John Conway s'était rendu compte de la possibilité de modéliser, dans le Jeu de la vie, les principaux connecteurs logiques ("portes logiques") : NON, ET, OU.

Il en avait déduit la possibilité théorique de réaliser, avec les éléments du Jeu de la vie, un ordinateur universel (une machine de Turing).

L'automate était donc à même de trouver le résultat de toute fonction calculable par programme.

En outre, le problème  de la stabilisation (notamment, de l'extinction) d'une population du Jeu de la vie était ainsi ramené au problème de l'arrêt d'une machine de Turing. Un résultat notoirement indécidable. Remarquons qu'il ne suffit pas, pour le résoudre, de faire fonctionner un simulateur de Jeu de la vie sur la configuration étudiée. En effet, si celle-ci ne se stabilisait pas, le programme tournerait indéfiniment, sans jamais donner de réponse.

D'un point de vue pratique, on peut difficilement appeler "machine" une configuration qui calcule indirectement une valeur donnée par le biais de son taux de croissance.

haut de page

Premières machines

De la possibilité théorique de machines calculatrices à leur réalisation effective, plus de 20 années de recherches se sont écoulées.

Le primer est la première machine capable de calculer les nombres premiers. Elle a été construite en 1991 par Dean Hickerson. La population initiale est de 2970 cellules :

génération 0

Elle fonctionne comme un canon émettant périodiquement des navires, énumérant ainsi les entiers. Dans le même temps, la partie principale s'étend et émet d'autres trains de navires à des intervalles proportionnels aux entiers déjà engendrés. Ces deuxièmes vagues de navires vont rattraper et détruire certains de ceux de la première série. Précisément : ceux dont l'instant d'émission est multiple d'un autre entier déjà engendré, càd : n'est pas un nombre premier. Ce "filtre" réalise ainsi le crible d'Eratosthène dans le Jeu de la vie. On voit s'éloigner les navires espacés comme les nombres premiers [1].

génération 2048

Cette configuration a été simplifiée [2] par Jason Summers en 2005. Ce sont là des glisseurs dont les espacements représentent les entiers premiers.

Ci-dessous, la dernière version, datant de février 2010 (population initiale : 3671 cellules) :

génération 528

Si mesurer les espaces entre glisseurs vous ennuie... que dites-vous de cette version [3] pourvue d'un "affichage digital" ?

(vue partielle)

Le même J. Summers est l'auteur (en 2010) d'une machine calculant les nombres de Fermat premiers. Un nombre de Fermat est un entier Fn = 2^(2n + 1). Seuls F0 à F4 sont premiers [4]. On a montré que Fn était composé pour tout n < 34. La machine de J. Summers est conçue pour se désintégrer si elle rencontre un nombre de Fermat premier > F4. D'ici là, elle fonctionnera donc pendant au moins 101 190 817 788 générations...

génération 0 - population 10 001

J. Summers reliait ainsi le destin d'une configuration particulière du Jeu de la vie à une conjecture mathématique ouverte. Son propos était d'illustrer par ce moyen l'imprévisibilité du comportement d'une population au jeu de la vie.

haut de page

Machines universelles

En avril 2000 P. Rendell conçu la première machine de Turing dans le Jeu de la vie. Sa conception respectait tous les éléments d'un tel "ordinateur universel" : bande, tête de lecture, registre, processeur.

Dotée initialement de 36 549 cellules, voici sa génération n° 24 011 860 569 017 835 123 423 611 411 515 902 016 calculée en moins de 30s par le programme Golly.

En juin 2009, "Calcyman" [5] a achevé la mise au point d'un calculateur/constructeur universel, à même de réaliser n'importe quel calcul dans le cadre du Jeu de la vie, et de construire des configurations pour le même jeu selon le résultat de ces calculs. Vous pouvez l'admirer ici.

Ces machines "universelles" n'ont pas mis fin à la recherche de machines spécialisées, plus efficaces dans la réalisation d'un calcul donné.

Notes

[1]  2 et 3 ne sont pas produits, la série commence à 5

[2]  dans son principe seulement -- la population initiale est encore plus élevée

[3]  qui, notons-le, utilise un ensemble de règles légèrement différentes de celles du Jeu de la vie

[4]  P. de Fermat avait noté ce fait, et conjecturé en 1640 que tous les nombres de cette forme étaient premiers. En 1732, Euler avait prouvé que F5 était composé. La conjecture de Fermat s'est révélée une des plus malheureuses de l'histoire des mathématiques. En effet, actuellement, on n'a découvert aucun autre nombre de Fermat premier que F0, ..., F4 !

[5]  un pseudo...

haut de page