La fourmi de Langton

Grâce aux automates cellulaires, la cybernétique montre que quelques règles élémentaires simples peuvent conduire à des comportements émergents assez inattendus.

Et certains attracteurs, bien que n'étant pas "étranges" sont toutefois étonnants.
En voici un exemple: la fourmi de Langton est un automate cellulaire dont l'évolution semble régie par un attracteur.
Les règles de la fourmi de Langton sont simples:
Prenez une grille infinie remplie de cases blanches avec une fourmi sur l'une des cases.
A chaque itération, on applique les règles suivantes:

1. Si la fourmi se trouve sur une case noire, elle tourne à gauche et avance d'une case; la case qu'elle quitte change de couleur et devient blanche.
2. Si la fourmi se trouve sur une case blanche elle tourne à droite et avance d'une case; la case qu'elle quitte change de couleur et devient noire.

Ça donne ça:


Après un démarrage chaotique, et quelle que soit la configuration de grille initiale, la fourmi finit toujours par construire une autoroute: Cliquez ici pour voir l'animation (on voit en haut à gauche le compteur du nombre d'itérations qui défile. Au bout d'environ 10 000 itérations, la fourmi construit toujours le même motif qui forme une route)

Il semblerait que cette route soit un attracteur de la fourmi de Langton.
Les quelques règles de base du niveau élémentaire ne permettent pas de prédire ce comportement émergent à l'échelle macroscopique.

Parmi les autres variétés d'automates cellulaires, on trouve les vers de Paterson. (Je cite ce turmite simplement parce que je le trouve beau, évoluant dans son espace triangulaire: Voir ici une superbe animation en mouvement)

Mais l'automate cellulaire le plus fascinant est le jeu de la vie.
Imaginé par John Conway, le jeu de la vie fonctionne avec quelques règles simples:
A chaque itération:

1. Une cellule morte ayant exactement trois voisines vivantes devient vivante (naissance).
2. Une cellule vivante qui a deux ou trois voisines vivantes survit (survie)
3. Dans tous les autres cas, la case meurt ou reste morte (mort)

Ces quelques règles permettent de créer des oscillateurs:

Des structures stables:

Mais il existe également des structures appelées vaisseaux, qui changent de forme pendant quelques générations en se déplaçant le long d'une diagonale et retrouvent leur forme d'origine. Exemple: le planeur qui est le plus petit vaisseau du jeu de la vie. (cliquez sur le lien pour le voir se déplacer)

Il existe également d'autres objets plus complexes comme des canons à vaisseaux, des puffers et des mathusalems.

Le jeu de la vie est également capable de produire des constructeurs universels, c'est à dire des structures capables d'autoréplication. 

Une estimation faite d'après les calculs de John Von Neumann prédit qu'il faut environ 10 milliards de cases pour produire une structure auto-reproductrice dans le jeu de la vie. C'est environ le nombre de molécules d'une cellule humaine...

A titre anecdotique, parmi les automates autoréplicants, on trouve les Quines dont l'existence a été démontrée par le théorème de récursion de Kleene, qui sont des programmes informatiques qui se répliquent eux-mêmes. (voir par exemple cette page html qui affiche son propre contenu: faire click droit->View source)

Mais l'exemple du jeu de la vie montre comment un ensemble de lois simples au niveau élémentaire peut faire émerger des structures plus complexes à un niveau supérieur. 

Ces nouvelles structures émergentes, macroscopiques, obéissent alors à d'autres lois (nouvelles) qui sont irréductibles à celles en vigueur au niveau élémentaire...

Source (entre autres):

Y a-t-il un grand architecte de l'univers - Stephen Hawking et Léonard Mlodinow