samedi 28 décembre 2013

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

22 commentaires:

  1. Prochain article demain samedi !

    RépondreSupprimer
  2. Avec toutes ces observations, tu vas finir par une critique de l'ordre social, nan ?

    RépondreSupprimer
    Réponses
    1. Ca dépend de ce que tu appelles l'ordre social. Je vois que tu fais déjà ça très bien sur ton blog, bien que je ne serais pas si radical. :-)
      Je pense qu'on peut en effet s'inspirer de l'organisation de la nature sans toutefois tomber dans le piège qui consiste à dire que ce serait "la même chose".
      La découverte initiale de l'entropie a eu des conséquences malheureuses sur la société: l'entropie avait plutôt "mauvaise réputation", toutes choses tendaient vers le chaos à moins d'y apporter une contrainte externe. On en a tiré une philosophie de gestion des hommes en entreprise de type "directif".
      On s'aperçoit aujourd'hui à quel point cette vision des choses était partielle et erronée.

      Supprimer
    2. Oui pardon. Par "critique" j'entendais seulement "analyse" ou "étude".

      En fait c'est cette phrase:

      "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."

      qui m'a fait pensé que tu n'étais pas loin de parler de la manière dont les hommes font société et des lois qui amènent les individus à vivre dans des structures complexes.

      c'est tout, ceci dit rejoins la révolution camarade ;)

      Supprimer
    3. Ah parce que vous trouvez ça complexe une ligne droite ?
      En fait, on est en train de s'extasier devant un programme à qui on a demandé de tracer une autoroute et qui...trace une autoroute.
      Il me semble évident que dans une configuration donnée, le programme va s'auto-répliquer ou rentrer dans une boucle. Mais bon, apparemment, ce n'est pas évident pour tout le monde. (attracteur)
      En plus, on appelle ça "fourmi", histoire de faire plus poétique peut-être ou de faire croire qu'il s'agit d'une loi de la nature, alors qu'en fait, il ne s'agit que d'un programme informatique et d'un "curseur".
      J'avais mal compris le truc au début. Je pensais que d'une situation aléatoire naissait inéluctablement un ordre. Mais ce n'est pas ça. Ma déception est grande. Je vais demander le remboursement de ma cotisation.

      Supprimer
    4. Je retire le terme "c'est évident" de mon commentaire précédent.
      Disons plutôt que la probabilité de voir apparaître une figure géométrique particulière (ligne droite, cercle, spirale,...) est non négligeable.

      Supprimer
    5. Ben oui, il n'y a rien d'évident à ce comportement justement. Il n'y a même pas de bonne probabilité de voir une telle régularité s'installer.
      L'intérêt des automates cellulaires réside justement dans le fait qu'on ne peut pas déduire leur comportement émergeant à partir des règles élémentaires pourtant déterministes qu'on a fixées.
      On a justement PAS demandé à un programme de tracer une autoroute: c'est un résultat purement empirique.
      De même qu'on n'a pas demandé au Jeu de la Vie de générer des Mathusalem et des Vaisseaux ou des Canon à vaisseaux. Ce genre de "vie" émerge des règles élémentaires sans qu'on soit capable de le prévoir le moins du monde.
      Ce qui est intéressant, c'est justement que -malgré- des règles élémentaires et déterministes (justement non aléatoires), on ne peut pas prévoir cette émergence. Autrement dit, même en simplifiant le monde physique à l'extrême, on ne serait pas capable de prévoir l'émergence des molécules d'ADN à partir d'une soupe primordiale d'atomes...

      C'est à mon avis une sérieuse critique au réductionnisme (la recherche de la compréhension des particules élémentaires pour expliquer l'univers) et si je travaillais à Genève, j'arrêterais immédiatement le recherche concernant le boson (la soit-disant particule de Dieu) ! On constate d'ailleurs que depuis la soit-disant "découverte" du boson (c'était quand déjà?), on a rien découvert de nouveau et de révolutionnaire en physique...

      Tu ne seras pas remboursé de ta cotisation! :-)

      Supprimer
    6. J'ajoute après vérification qu'on dit "soi-disant" et pas "soit-disant"... :-)

      Supprimer
    7. Scousez-moi d'insister Missié, mais jouons à un jeu. Non pas en 2D mais en 1D.
      Prenez une ligne constituée de x cases (ou x milles cases).
      Au départ, une case est noire, toutes les autres sont blanches.
      On applique les règles suivantes:
      Mon curseur va de la gauche vers la droite et rebondit lorsqu'il arrive au bout.
      Lorsqu'il rencontre une case blanche, rien ne se passe.
      Lorsqu'il rencontre une case noire, la 7ème après lui devient noire, et la 2ème avant lui inverse sa couleur.
      Appelons notre curseur une fourmi (Ça, c'est très important. Ça met un peu d'humanité dans ce monde de brutes).
      Y a-t-il ou pas selon tes termes, une bonne probabilité de voir une régularité s'installer ?
      Résultat: au bout d'un certain nombre de coups, toutes les case sont noires.
      Pourtant tu n'as pas non plus demandé au programme de te dessiner une ligne noire (??)
      Peut-on ou pas prévoir l'émergence de cette ligne toute noire ?
      Mais cela dit, je comprend bien ton propos pour illustrer cette critique du réductionnisme.
      Vivement le prochain article !...soi-disant.

      Supprimer
    8. Moi j'arrive pas à me représenter une fourmi en 1D: j'ai beau essayer, ça le fait pas...
      :-)
      Et en plus, on dit "des CanonS" avec un "S" puisqu'il y en a plusieurs. Il manque un correcteur orthographique qui corrige mes commentaires.

      Supprimer
    9. :-)
      Il faut les écrire avec Word et faire un copier/coller/merder.
      C'est une variété de fourmi très fine. On appelle ça : fourmi de Moebius.

      Supprimer
  3. Si seulement il finissait par une critique de l'ordre social ! Parce que moi, question fourmis, je suis un peu sec pour commenter.

    RépondreSupprimer
    Réponses
    1. L'organisation sociale des fourmis est très intéressante et discutable pourtant. Je suis sûr que tes lectures à ce sujet doivent pouvoir t'inspirer :-)

      Supprimer
    2. C'est pas un truc pour Fred ça ?

      Supprimer
    3. Si, mais j'ai découvert avec stupeur que les fourmis n'arrivent pas à disjoindre leur travail de leur existence

      Supprimer
  4. Quand ont regarde le code source de la fourmi de Langton, on s'aperçoit, et c'est bien normal, que c'est une fonction aléatoire qui détermine si la fourmi va aller à gauche ou bien à droite. Or, cette fonction aléatoire est-elle bien non déterministe ?
    Cette fonction n'a d'aléatoire que son nom. A-t-on fait l'essai avec une vrai fourmi posée sur un damier ?
    Je me souviens d'une devinette/tour de magie où on te demandait de choisir un nombre au Hasard, puis de le multiplier par 7, 9 ou 30 ou XXx, de retrancher ton age puis celui de ta belle mère, et on arrivait immanquablement à ta date de naissance ou bien à savoir quel jour de la semaine tu étais né. (peu importe).
    On est un peu stupéfait au début parce qu'on part d'un nombre "aléatoire", mais en fait, il y a une logique à tout ça. Et en analysant bien, on se rend compte qu'il ne peut pas en être autrement.

    RépondreSupprimer
    Réponses
    1. A quel code source fais-tu référence?
      Ce n'est pas une fonction aléatoire qui détermine si elle va à gauche ou à droite, ça dépend de la case sur laquelle elle se trouve.

      Supprimer
    2. Ah effectivement. Je n'avais pas tout compris. Je pensais qu'il y avait une part de hasard là dedans alors qu'il n'y en a pas. Il n'est donc pas surprenant d'avoir un attracteur et de terminer par une autoroute.
      C'est le terme de "démarrage chaotique" qui m'a perturbé. En fait, il n'y a rien de chaotique dans tout cela. 2 fois la même grille donneront 2 fois le même résultat.

      Supprimer
  5. Autre expérience qu'on pourrait faire dans le même ordre d'idée:
    Prenez tous les résultats du loto (Il doit bien y en avoir quelques milliers)
    Si la boule est paire, tourner à droite.
    Si la boule est impaire, tournez à gauche.
    (éliminer le n°49 pour avoir autant de n° pairs que d'impairs. C'est une barrière de potentiel franchissable :))
    Obtient-on les mêmes autoroutes ?
    Si oui, c'est un résultat intéressant pour ceux qui jouent au Loto.

    RépondreSupprimer
    Réponses
    1. Ca a l'air de marcher! Je viens de tirer les 7 bons numéros! :-)

      Supprimer
  6. Réponses
    1. Ah oui, pas mal. Il y a cette vidéo qui est très bien aussi:
      http://www.youtube.com/watch?v=xRO_qUneQ_A

      Supprimer