Les automates cellulaires

IDLabs

Automates Cellulaires

 

 

I. L'origine des automates cellulaires

A. John Von Neumann

Né à Budapest le 28 décembre 1903, John Von Neumann démontre des capacités cognitives incroyables. Il devient rapidement l’un des plus grands génies de l’époque, décroche le plus prestigieux titre de mathématiques de Hongrie à dix-neuf ans, puis un doctorat trois ans plus tard.

Il part de Berlin en 1931 pour se rendre en Amérique, à Princeton. En parallèle à ses recherches mathématiques, il mène des recherches sur les réactions de deux acteurs rationnels et donne donc naissance à la théorie des jeux avec l’aide d’Oskar Morgenstern, mathématicien et économiste.

Contrairement à son très réputé confrère, Einstein, il ne semble montrer aucun remord à mettre son génie au service de l’armée. Il participe donc au projet Manhattan en plus d’apporter son aide sur la théorie des ensembles de Gödel, de participer au fondement de la mécanique quantique, d’utiliser son génie mathématique pour écrire la théorie des jeux et de poser les bases des intelligences artificielles. Et c’est surtout ce dernier point qui nous intéresse ici.

En effet, Homer Jacobsen avait déjà proposé l’idée de systèmes auto-répliquants, c'est-à-dire qu’ils pouvaient, avec les ressources environnantes, créer une copie d’eux-mêmes. En 1948, Neumann reprit ces travaux et se mit à réfléchir dessus. Il était facilement envisageable qu’une machine qui a pour but de concevoir quelque chose est plus complexe que le résultat fabriqué. Neumann se demanda s’il était possible de créer une machine qui, à défaut de réaliser mieux, réaliserait un objet équivalent à elle-même, autrement dit : elle-même. Mais cela nécessitait des systèmes beaucoup trop complexes pour le début des années 50 : il fallait que la machine puisse voir pour différencier les composants et qu’ensuite elle parvienne à les manipuler, même les plus fragiles, sans pour autant les abimer. A une époque où l’on ne différencie même pas encore les ordinateurs des simples calculateurs, c’était une pure utopie. Même si ce n’était donc qu’une théorie, ce fut le début de la théorie des automates.

B. Stanislaw Ulam

Né en 1909 en Pologne, Stanislaw Ulam était lui aussi un esprit brillant. Il entra comme étudiant aux Etats-Unis en 1938. Il devint rapidement un ami proche de Neumann qui reconnait son génie et surtout sa créativité. Il écrivit avec Nicholas Metropolis la méthode de Monte-Carlo qui permit de grandes avancées dans le domaine de la fission nucléaire sur lequel il travailla après avoir été invité par Neumann. Cette méthode permettait de résoudre certains problèmes trop complexes en se basant sur des nombres aléatoires. Par la suite, c’est lui qui démontra que le modèle de bombe H d’Edward Teller était inutilisable et qui proposa donc une nouvelle version. Il est aussi celui qui a inspiré le projet Orion, premier projet spatial qui aurait dû utiliser le nucléaire pour se propulser.

Il ne travailla pas sur les automates cellulaires et pourtant, il permit leur développement en étudiant les objets géométriques définis de façon récursive. En effet, ces objets possédaient des règles simples et avaient pour but de se développer, de se reproduire et de se combattre pour “conquérir” du territoire avant de finalement mourir. Il était facile de remarquer que cela s’apparentait fortement aux organismes vivants comme les humains. Ulam plaça cette étude dans un univers composé de plusieurs cellules où ces dernières ne pouvaient être qu’actives ou passives. Les objets étaient définis par les cellules actives et chaque cellule voyait son prochain état dicté par l’état des cellules avoisinantes et le sien au “tour” actuel. Il remarqua alors que ce “monde” possédait ses propres règles et s’affranchissait de certaines du notre. Pour autant, les possibilités en restaient très nombreuses et en modifiant certaines choses, il pouvait rapidement devenir plus complexe. Ulam présenta alors ses travaux à Neumann. Il ne fallut pas beaucoup de temps pour que celui-ci adopte cet univers pour son automate. Sans travailler dessus, Ulam venait de donner un énorme coup de pouce au domaine des automates cellulaires.

 

C. Le constructeur universel

Neumann s’attela alors à la fabrication de son automate auto-reproductif. Mais même dans cet univers alternatif, il se posait un problème : le constructeur universel avait besoin de sa propre définition pour pouvoir se reconstruire. La machine globale était en ce cas composée du système de reproduction et de la définition de la machine en général, c'est-à-dire du système de reproduction et de la définition de la machine en général et ainsi de suite ! On pouvait décomposer la définition à l’infini et cela empêchait le système de faire quoi que ce soit. Neumann eu alors l’idée de s’inspirer de l’un des pères de l’informatique : Alan Turing. Ce dernier avait inventé les “machines de Turing”. Ces machines pouvaient en théorie résoudre de manière virtuelle n’importe quel calcul en le décomposant en une suite algorithmique utilisant des opérations définies, elle en devenait donc universelle. Le fait que le type d’opération soit limité permettait à Neumann d’intégrer une machine de Turing à son système.

De cette façon, le constructeur put être finalisé. Il comportait donc quatre parties : La première était la description : elle définissait la machine sous la forme d’une longue bande et était lue par la seconde partie : la machine en elle-même. Celle-ci devait pouvoir lire la bande mémoire et l’interpréter pour ordonner la troisième partie : le bras constructeur. Ce “bras” se déplace dans un espace vide sous les ordres de la machine pour pouvoir placer les nouveaux éléments de la copie. Pour finir, on trouvait la machine universelle de Turing qui comprenait qu’une fois la définition du constructeur lue dans sa totalité, celle-ci ne devait plus être interprétée mais recopiée. La machine ordonnait donc à partir de ce moment au bras de recopier la mémoire et la copie était achevée.

Dans sa version finale, le constructeur universel se trouvait dans une grille en deux dimensions d’au moins 200 000 cellules pouvant varier entre vingt-neuf états. Elles suivaient une règle leur dictant leur prochain état en fonction de leur propre état à ce tour là et de celui de ses cellules cardinales voisines. Evidemment, cela faisait beaucoup de règles de transitions : 295 soit 20 511 194 possibilités.

 

Malheureusement, étant donné sa complexité et son nombre d’informations nécessaires insensé, personne ne parvint à le simuler dans son intégralité. Neumann lui-même abandonna ses travaux une fois le constructeur universel achevé. Malgré tout, même si le premier automate cellulaire était impossible à simuler, les bases étaient posées. De nos jours, il nous est possible de simuler une partie de la phase de reproduction.

II. Les automates cellulaires de nos jours

A. Le jeu de la vie

Le fait que Neumann abandonne ses travaux ne valorisa pas les automates cellulaires les années suivantes. L’informatique étant en plein essor, l’attention du public n’en fut que plus détournée. Ce n’est qu’à partir de 1970 qu’ils revinrent au gout jour quand le mathématicien John Horton Conway. Celui-ci était en effet très intéressé par les recherches de Neumann. Il décida de les simplifier en s’aidant de celles de John Leech pour finalement arriver à un automate cellulaire en apparence des plus simples : le jeu de la vie.

Cet automate cellulaire ne possédait que deux états possibles : vivant et mort. Contrairement au constructeur universel, les cellules tenaient compte de leur propre état mais aussi de celui des huit autres cellules environnantes. Conway lui donna trois règles de transition :

  • Si une cellule vivante ne possédait qu’une seule cellule voisine (c'est-à-dire elle-même vu qu’elle tenait compte de leur état), elle mourrait de l’isolement.
  • Si une cellule vivante possédait quatre ou plus cellules voisines, elle mourait de surpopulation.
  • Si une cellule morte était entourée de trois cellules vivantes, elle prenait vie comme pour une reproduction trisexuée.

Pour la première fois dans l’étude des automates cellulaires, le but n’était pas de chercher comment arriver à un point donné mais de partir d’une situation et de regarder ce que cela peut donner. Et sur ce plan, le jeu de la vie réservait quelques surprises. En effet, peu de temps après sa réalisation, on remarqua que certaines structures stables apparaissaient selon l’état de départ. La plus basique d’entre elles était un simple carré de quatre cellules mais on ne tarda pas à en découvrir d’autres.

Par la suite vinrent les oscillateurs, des structures périodiques et infinies.

En troisième lieu, il fut découvert des figures stables se translatant. La plus célèbre d’entre elles est surement le planneur. Il faut dire qu’après la sortie du jeu de la vie, les automates cellulaires firent leur grand retour sur scène. De très nombreux scientifiques tentèrent de trouver de nouveaux motifs pour avoir l’illustre honneur de les nommer. Il en existe d’ailleurs beaucoup trop pour tous les présenter, la plupart n’ayant aucun intérêt.

Ce n’est que plus tard que l’une des affirmations de Conway fut mise en doute : il assurait qu’il existait des figures permettant une expansion infinie. Le but des scientifiques devint donc de prouver cette hypothèse ou, à défaut, de l’invalider. William Gosper et ses collègues découvrirent alors le canon à planneurs. Cette figure “lançait” un planneur toutes les trente générations. L’hypothèse de Conway fut donc validée.

La deuxième découverte fut celle des “Jardins d’Eden”. C’est en 1962 que ce thème fut pour la première fois abordé par Moore qui faisait à cette époque référence aux automates reproducteurs comme le constructeur universel. En 1970, le mathématicien Alvy Ray Smith reprit cette notion et la démontra comme applicable au jeu de la vie. Le principe n’était pas de trouver des jardins d’Eden, mais de prouver que certaines configurations ne pouvaient tout simplement pas être autre chose que la première génération, qu’elle ne pouvait descendre d’aucune autre configuration. Peu après cette démonstration, de nombreux exemples furent trouvés, nécessitant à chaque fois la preuve que ces figures ne peuvent en aucun cas être descendantes.

La troisième découverte, et surement la plus importante fut la calculabilité. En effet, dans son constructeur universel, Neumann avait intégré une machine de Turing universelle, capable de résoudre n’importe quel calcul. Cependant, il possédait une complexité à toute épreuve. Ce ne fut qu’en 1982 ou Conway lui-même démontra que le jeu de la vie en était lui aussi capable en reprenant une donnée simple utilisée elle aussi en informatique : le bit. Dans le jeu de la vie, celui-ci était matérialisé par un planneur et une information complète pouvait être transmise avec un faisceau de planneur généré par un certain type de canon.

 

B. La fourmi de Langton

Comme le montra le jeu de la vie, certains automates cellulaires d’un simplicité apparente pouvaient posséder des comportements beaucoup plus complexes. En effet, prenons par exemple la fourmi de Langton. Le principe était simple, on possédait une grille bidimensionnelle qui s’agrandissait chaque fois que la fourmi en atteignait les bords et au centre, une case noire. Les règles étaient celles-ci :

  • Si la fourmi était sur une case blanche, elle effectuait une rotation vers la droite, sinon, elle l’effectuait sur la gauche.
  • Elle changeait la couleur de la case sur laquelle elle se trouvait actuellement.
  • Elle avançait d’une case.

Sous ces apparences simples se cache un comportement encore incompris. La fourmi procédait pendant environ 500 tours à la construction de modèles symétriques et presque artistiques :

Cependant, par la suite, elle entamait une phase de chaos total, élargissant énormément son champ d’action et se déplaçant de façon incompréhensible. Mais le meilleur restait pour la fin. Après 10 000 tours, la fourmi entamait la construction d’un schéma toujours identique, se répétant à l’infini avec un pas de 104 tours et qui fut nommé “l’autoroute”. La où ce comportement devient intéressant, c’est lorsque l’on change la grille de départ en ajoutant d’autres cases noires. Cela peut changer, voir annuler les deux premières phases. En revanche, peu importait les conditions de départ, l’autoroute apparaissait toujours. En réalisant cet automate cellulaire avec plusieurs fourmis en simultanée, elles réalisaient toutes une autoroute à un moment ou un autre. Ce comportement fut rapidement assimilé à un attracteur, un comportement qui se réalisera dans tous les cas et qui est l’une des bases de la théorie du chaos. Même si elle n’apporta aucune avancée dans le domaine des automates cellulaires, sa simple trouvaille prouva aux scientifiques que ce domaine n’était pas mort car il existait encore des comportements incompréhensibles.

C. Applications

Malgré tout ce qui fut trouvé sur les automates cellulaires, il était difficile de leur trouver une réelle utilité. Ou du moins c’était le cas jusqu’à une certaine question : dans le constructeur universel, la régression infinie de la définition avait été un problème majeur auquel il avait pallié en ajoutant une machine de Turing universelle qui s’assurait que la définition soit tout simplement copiée. Or, il existe un autre système autoreproducteur omniprésent dans notre vie, et ce sont nos cellules. La question se posa alors : Est-ce que Neumann venait tout simplement de proposer une version complètement différente de ce qu’il se passait en permanence dans notre corps, ou venait-il de réaliser un véritable coup de génie, démontrant que son constructeur universel s’approchait plus de la réalité qu’on ne le pensait et que certains mécanismes biologiques peuvent être déduis à partir de raisonnements logiques comme ceux qui menèrent Neumann à son célèbre automate cellulaire ?

La réponse vint de Poundstone qui déclara :

« La solution de von Neumann est une belle astuce, mais elle est bien plus que cela. Elle constitue la méthode par laquelle la vie authentique, organique se reproduit. »

Et en effet, après de longues études sur la biologie et particulièrement sur ce qui nous compose, Il fut trouvé des équivalents entre le constructeur universel et nos cellules : Toutes nos cellules sont strictement identiques à leur création. Elles possèdent de ce fait le même moyen de reproduction. Au lieu d’une longue bande horizontale, c’est une double hélice appelée ADN qui contient la description de la cellule. Le constructeur universel est quant à lui comparé au ribosome. Le ribosome reçoit grâce à l’ARN messager les informations concernant l’ADN qu’il interprète avant d’utiliser les vingt acides aminés trouvables dans nos cellules pour pouvoir construire les protéines voulues. Cependant, il existe des éléments qui ne peuvent pas être produits par ces acides, en particulier l’ADN. Or, si la cellule ne reproduit pas sa définition, la cellule “fille” ne pourra pas à son tour se reproduire. C’est donc le rôle de l’ADN polymérase qui a pour charge de copier l’ADN sans l’interpréter, elle fait donc office de machine de Turing universelle alliée au système de copie du constructeur universel.

Les seules différences notables dans ce système étaient que dans le constructeur universel, la copie de la définition se faisait à la fin de la copie du système alors que dans nos cellules, la copie de l’ADN se fait en simultané. Neumann venait donc de prouver que le vivant et l’inerte n’était pas séparé par un si grand fossé, et surtout que les automates cellulaires comme le sien n’était pas si loin d’un organisme vivant.

A ce moment-là, un autre sujet intervint : en discutant du phénomène d’émergence, on se rendit rapidement compte que certains automates cellulaires comme le jeu de la vie donne quasiment toujours des figures stables à condition de le laisser tourner assez longtemps. Conway, déclara alors que si l’on simulait le jeu de la vie dans un univers beaucoup plus grand, on pourrait alors voir apparaître des organismes vivants qui se développeraient, se reproduiraient et ainsi de suite, comme ce que nous appelions nous aussi des organismes vivants. Autrement dit, un automate cellulaire aurait les capacités de simuler un nouveau monde, voire presque de le créer. Et cela fit écho à une autre théorie, développée par Konrad Zuse qui, en voyant les travaux menés sur les automates cellulaires, annonça que notre monde, et non pas au sens de la planète Terre mais à celui de tout ce qui existe, n’était surement que l’œuvre d’un automate cellulaire d’une taille inimaginable à notre échelle. Cette mise en abyme donnait en effet de quoi réfléchir puisque, si nous étions capables de simuler un univers sur un ordinateur avec un automate cellulaire, rien ne nous prouvait que nous étions le stade le plus haut de la mise en abyme, rien ne démontrait que nous n’étions pas nous-même une simulation.

 

Conclusion

En fin de compte, même malgré tout ce qui a été dit ici, on ne peut que constater que les automates cellulaires n’en sont pas pour autant utilisés de partout. Il existe de nombreuses simulations réalisées avec ceux-ci, comme pour des feux de forêts ou la circulation sur le périphérique, mais d’aucun ne revêt une réelle importance. Ce n’est pas pour autant que nous ne devons pas reconnaître l’importance de ceux-ci car force nous est de constater qu’ils étaient en avance sur notre temps. Nul ne peut contredire le fait que Neumann, avec une logique implacable parvint à construire un automate cellulaire reproduisant à quelques détails près le système de reproduction de nos cellules jusque-là inconnues.

Peut-être que les automates cellulaires sont aujourd’hui en arrière-plan, mais il y a fort à parier qu’ils referont surface un jour, comme ils semblent le faire depuis des années, nous prouvant encore leur avance sur nos connaissances.

 

Bibliographie

Wikipédia - Automate cellulaire : https://fr.wikipedia.org/wiki/Automate_cellulaire#

Futura Tech - Automate cellulaire : http://www.futura-sciences.com/tech/definitions/informatique-automate-cellulaire-8909/

Science étonnante - Automate cellulaire : https://sciencetonnante.wordpress.com/2013/10/28/les-automates-cellulaires-elementaires/

Futura Tech - John Von Neumann : http://www.futura-sciences.com/sciences/personnalites/matiere-john-von-neumann-256/

Larousse - John Von Neumann : http://www.larousse.fr/encyclopedie/personnage/John_Von_Neumann/181003

Biowall : http://lslwww.epfl.ch/biowall/VersionF/ApplicationsF/UConstF.html

Mémoire sur les automates cellulaires de Nazim Fates : http://nazim.fates.free.fr/Epistemo/MemoireAC/FatesMemoireAC.doc

Wikipédia - Fourmi de Langton : https://fr.wikipedia.org/wiki/Fourmi_de_Langton

Sience étonnante - Fourmi de Langton : https://sciencetonnante.wordpress.com/2011/03/21/la-fourmi-de-langton/

Wikipédia - Ribosome : https://fr.wikipedia.org/wiki/Ribosome

Wikipédia - ARN : https://fr.wikipedia.org/wiki/Acide_ribonucl%C3%A9ique

Wikipédia - ARN messager : https://fr.wikipedia.org/wiki/Acide_ribonucl%C3%A9ique_messager

Wikipédia - ADN : https://fr.wikipedia.org/wiki/Acide_d%C3%A9soxyribonucl%C3%A9ique

Wikipédia - ADN polymérase : https://fr.wikipedia.org/wiki/ADN_polym%C3%A9rase

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *