Les automates cellulaires

Les automates cellulaires sont des grilles contenant des cellules ayant chacune un état et qui peuvent évoluer au cours du temps (via un programme pour plus de facilités).

Ils sont régis la plupart du temps par des règles simples et visent à simuler la complexité qui peut émerger de structures basiques.

Le jeu de la vie

 

Inventé par John Conway en 1970, il tire son nom par analogie à la vie elle-même qui a commencé avec des choses simples comme les cellules pour donner des êtres complexes tel que l’être humain.

Cette simulation commence sur un plateau carré composé de cellules qui suivent 2 règles :

  • Chaque cellule ayant 2 ou 3 voisins survie (qu’ils soit diagonaux, horizontaux ou verticaux) sinon elle meurt.
  • Chaque cellule non occupée qui a exactement 3 voisins voit naître une nouvelle cellule.

Les changements vont donc s’opérer à chaque tour.

Voici 2 exemples pour illustrer ces règles :

En haut nous avons la situation de départ, en dessous la conséquence de ces situations sur les cellules. Les cellules rouges meurent par cause d’isolement, en effet elles n’ont qu’un seul voisin direct. Celle du milieu a en revanche deux voisins donc elle survie.

En vert une cellule se crée car elle possède exactement 3 voisins (n’oubliez pas que la diagonale compte).

 

Maintenant que c’est un peu plus clair, considérons l’exemple de plateau de départ suivant :

On applique ensuite les règles de naissance et de mort pour le prochain tour, on obtient ce schéma :

En rouge nous avons les cellules qui vont mourir d’isolement (moins de 2 voisins) et en vert les cellules qui vont se créer (exactement 3 voisins).

Le plateau après le tour 1 ressemble finalement à ça :

Au tour suivant on recommence, on applique les mêmes règles :

Cette fois-ci on a en bleu des cellules qui meurent par surpopulation (plus de 3 voisins) et en vert toujours les cellules qui se créent. Il n’y a en revanche aucune cellule qui meurt par isolement.

Et ainsi de suite jusqu’à ce que l’on tombe sur l’un des cas suivants :

  • Les cellules finissent par toutes mourir, c’est le cas ici quelques tours plus tard :

  • Les cellules forment une structure où rien ne se perd et rien ne se crée :

Situation de départ

Évolution

On constate que les cellules terminent leur progression par un carré qui n’évoluera plus, c’est ce qu’on appelle une structure stable.

  • Les cellules forment une structure à oscillation ou à évolution infinie :

Situation de départ:

Évolution:

Autre exemple.

Situation de départ:

Évolution:

Jusqu’ici nous avons vu des structures ayant que de petites conséquences, illustrant mal le concept principal de ce « jeu », le fait de démontrer que des structures et règles simples peuvent engranger de grandes choses.

L’exemple suivant est totalement différent :

Malgré cette structure simple on obtient un système qui meurt au bout d’une soixantaine de cycles :

D’autres structures encore tendent vers une production de cellules à l’infini :

C’est à partir de là que le « jeu » prend tout son sens. En effet avec ce type d’évolution assimilable à un signal, on peut élaborer tout un monde complexe avec des portes logiques (ET, OU, NON OU etc…) et donc créer une machine de Turing (ordinateur virtuel).

Un exemple d’application :

Il est même possible de créer un jeu de la vie avec le jeu de la vie :

https://www.youtube.com/watch?v=xP5-iIeKXE8

La fourmi de Langton

 

La fourmi de Langton est un autre programme connu, avec deux règles encore plus simples :

  • Si la fourmi se trouve sur une case blanche elle tourne à droite et inverse la couleur de la case de laquelle elle vient de partir.
  • Si la fourmi se trouve sur une case noire elle tourne à gauche et inverse la couleur de la case de laquelle elle vient de partir.

Cette simulation pourtant simple soulève aussi beaucoup de questions. Pendant 500 cycles la fourmi semble faire des mouvements assez symétriques.

Passé ce cap elle fait des mouvements désordonnés et finalement au bout de 10 000 cycles elle crée une figure régulière qui tend vers l’infini. On l’appelle l’autoroute :

Le plus étonnant est que si on rajoute des couleurs avec leur mouvement associé (droite ou gauche) on finit toujours par obtenir le même résultat à un moment ou à un autre. On retombe toujours sur cette autoroute sans pouvoir l’expliquer.

Plus d’exemples : https://youtu.be/1X-gtr4pEBU

Ces deux simulations nous montrent à quel point des choses simples ont la possibilité d’élaborer des structures complexes, désordonnées ou ordonnées, des réplications infinies, des machines de Turing etc… à l’instar des cellules vivantes en apparence anodines mais qui sont à l’origine de la vie et de la complexité du monde.

 

Simulations en ligne :

https://bitstorm.org/gameoflife/

http://www.langtonant.com/

Source :

https://sciencetonnante.wordpress.com/2017/12/08/le-jeu-de-la-vie/

 

Leave a Reply

Your email address will not be published. Required fields are marked *