Jeu de la Vie — Conway (1970)
Le Jeu de la Vie est un automate cellulaire 2D conçu par John Horton Conway en 1970. Avec seulement 4 règles, il produit une richesse comportementale extraordinaire — et est Turing-complet.
Les 4 règles
Grille 2D, voisinage de Moore (8 voisins), deux états (vivant / mort) :
- Une cellule vivante avec 2 ou 3 voisins vivants survit
- Une cellule vivante avec < 2 voisins meurt (isolement)
- Une cellule vivante avec > 3 voisins meurt (surpopulation)
- Une cellule morte avec exactement 3 voisins naît
Les structures émergentes
Structures stables (Still lifes)
Ne changent pas d’état : bloc 2×2, ruche, pain, bateau…
Oscillateurs
Reviennent à leur état initial après N pas :
- Blinker (période 2) — le plus simple
- Toad (période 2)
- Pulsar (période 3)
Gliders — structures mobiles
Se déplacent sur la grille indéfiniment :
- Glider — se déplace en diagonale, période 4
- Lightweight spaceship (LWSS) — plus rapide, horizontal
Canons et synthèses
- Gosper Glider Gun — émet un glider toutes les 30 générations (découvert en 1970, preuve que le Jeu de la Vie est infini)
- Des structures peuvent construire d’autres structures
Turing-complétude
Le Jeu de la Vie peut simuler tout calcul possible :
- Les gliders encodent des bits d’information
- Les collisions entre gliders encodent des portes logiques (AND, OR, NOT)
- On peut construire une machine de Turing entière — ou même simuler le Jeu de la Vie lui-même
Pourquoi c’est philosophiquement fort
Le Jeu de la Vie montre que 4 règles locales suffisent pour engendrer toute la complexité calculable.
Si l’univers est un automate cellulaire, ses lois physiques pourraient être aussi simples — et toute la complexité que nous observons en serait une émergence.
C’est l’intuition centrale de Wolfram dans A New Kind of Science, et une question ouverte en physique fondamentale.
Concepts liés
Références
- Gardner, M. (1970). Mathematical Games. Scientific American, 223(4), 120–123. — première publication
- Berlekamp, E., Conway, J. H., & Guy, R. (1982). Winning Ways for your Mathematical Plays, Vol. 2.
- Rendell, P. (2002). Turing universality of the game of life. In Collision-Based Computing. Springer.