Le jeu de la vie

C’est ainsi, Game of Life (GoL), qu’a été baptisé l’automate cellulaire imaginé par John Conway. Un automate cellulaire est un modèle où étant donné un état, on passe à l’état suivant en appliquant un ensemble de règles.

Dans le cas du GoL, le modèle est une grille (un quadrillage) composée de cellules qui sont, soit allumées (vivantes), soit éteintes (mortes). Les règles pour calculer l’état suivant sont simples1 :

  • Une cellule morte possédant exactement trois voisines vivantes devient vivante (elle naît).
  • Une cellule vivante possédant deux ou trois voisines vivantes le reste, sinon elle meurt.

En fonction de la taille de la grille et de la configuration initiale des cellules, l’évolution du jeu peut donner des résultats très intéressants. En voici un exemple tiré de Wikipédia :

Gospers_glider_gun.gif

Au delà de son caractère amusant, le GoL présente des propriétés mathématiques très riches. Des structures stables et périodiques peuvent apparaître. Certaines ont même des noms très sympathiques : grenouilles, jardins d’Éden, etc.

Encore plus intéressant est le fait qu’il s’agit d’une machine de Turing universelle :

“il est possible de calculer tout algorithme pourvu que la grille soit suffisamment grande et les conditions initiales correctes”

et de là, il en découle, de par le problème de l’arrêt, qu’on ne peut pas prédire le comportement asymptotique de toute structure du jeu de la vie. Il s’agit d’un problème indécidable au sens algorithmique.

“Dire qu’un problème est indécidable ne veut pas dire que les questions posées sont insolubles mais seulement qu’il n’existe pas de méthode unique et bien définie, applicable d’une façon mécanique, pour répondre à toutes les questions, en nombre infini, rassemblées dans un même problème.”2

On voit bien que, même une machine complètement déterministe et extrêmement simple, peut être imprédictible.

Il y en a qui seraient tentés de dire qu’une telle machine pourrait avoir du libre arbitre. Bien entendu, les gens sensés, auront un sourire narquois en entendant de tels propos. Une grille de morpion qui voudrait s’émanciper!

Si on revient sur le côté amusant du jeu, on pourrait avoir envie d’en faire un objet physique. Avec l’électronique bon marché pour les bricoleurs, il ne doit pas être difficile de brancher quelques (centaines de) LEDs et les piloter avec un Arduino contenant le programme avec les règles du GoL.

On pourrait même utiliser une webcam pour prendre une photo de l’environnement, la binariser et en faire ainsi la configuration initiale pour la grille.

De là, il est difficile d’échapper à la tentation du selfie pour initialiser le système. Est-ce que si on sourit sur la photo ça converge vers un jardin d’Éden3? Est-ce que si on fait la gueule ça génère des canons? Est-ce que si on prend Papi en photo ça nous fait des Mathusalems?

Et sans s’en rendre compte, on a construit un système physique qui réagit à l’expression d’un visage et dont l’état asymptotique est indécidable! C’est presque le niveau de développement social d’un bébé de quelques semaines. Et on peut le débrancher la nuit4!

Footnotes:

1

Comme d’habitude, Wikipédia est votre amie : http://fr.wikipedia.org/wiki/Jeu_de_la_vie .

3

En fait, c’est impossible par définition, mais bon …

4

Ce n’est pas encore aussi abouti que ce que Charlotte proposait la semaine dernière, mais on s’en approche.