Aller au contenu
Doony

pour les matheux et les physiciens

Messages recommandés

Voila je viens de voir rayon x et si j'ai bien compris les hypothese approfondies soutenant la presence du mur de planck mettent en evidence une masse pour cette entité ... cette masse ayant une energie extraordinnaire dont l'origine reste a determiner !

celon leurs explication (aux freres bogdanov) : la masse si petite de ce mur s'expliquerait par l'incroyable energie qu'il contient... Or selon la theorie de la relativité ( E=mc²) l'energie est proportionnelle à la masse (c² étant une constante) ce qui signifirai alors que la masse augmante avec l'energie et inverssement : l'enerfie augmente avec la masse .. ce qui irait en contradiction avec ce qui est ennoncé par les frere bogdannv ... ce qui me parait peu probable .. donc j'imagine que l'erreur viens de moi : une mausaise comprehension ou une mauvaise interpretation de la theorie d la relativité.

j'aimerais donc (si l'un de vous l'a ) une explication afin de m'eclaircir ce point. :diable:

Partager ce message


Lien à poster

c'est claire c'était joli :diable::D:unsure::unsure::blink::blink:

Modifié par Doony

Partager ce message


Lien à poster

J'y crois moyennement à leur histoire de "code cosmologique" comme le code génétique... :diable:

Partager ce message


Lien à poster
J'y crois moyennement à leur histoire de "code cosmologique" comme le code génétique... :diable:

<{POST_SNAPBACK}>

peux-tu alors nous exposer ta théorie?

Partager ce message


Lien à poster
Voila je viens de voir rayon x et si j'ai bien compris les hypothese approfondies soutenant la presence du mur de planck mettent en evidence une masse pour cette entité ... cette masse ayant une energie extraordinnaire dont l'origine reste a determiner !

celon leurs explication (aux freres bogdanov) : la masse si petite  de ce mur s'expliquerait par l'incroyable energie qu'il contient... Or selon la theorie de la relativité ( E=mc²) l'energie est proportionnelle à la masse  (c² étant une constante) ce qui signifirai alors que la masse augmante avec l'energie et inverssement : l'enerfie augmente avec la masse .. ce qui irait en contradiction avec ce qui est ennoncé par les frere bogdannv ... ce qui me parait peu probable .. donc j'imagine que l'erreur viens de moi : une mausaise comprehension ou une mauvaise interpretation de la theorie d la relativité.

j'aimerais donc (si l'un de vous l'a ) une explication afin de m'eclaircir ce point.  :diable:

<{POST_SNAPBACK}>

E=m.c² ne s'applique pas dans ce cas c'est tout. Ca tu l'utilises dans le cas de la chute libre d'un objet par exemple. Enfin il me semble.

Partager ce message


Lien à poster
J'y crois moyennement à leur histoire de "code cosmologique" comme le code génétique... :diable:

<{POST_SNAPBACK}>

Des chercheurs ont mis au point des programmes informatiques qui s'appellent "automates cellulaires" et qui seraient capables de reproduire et d'expliquer n'importe quel phénomène de la vie. Ces automates cellulaires sont constitués de plusieurs cellules qui évoluent en fonction de l'état des cellules voisines (comme le jeu du démineur, vous voyez ?). Ces cellules évoluent donc selon certaines règles mathématiques (il en existe 256 différentes), et donc tout ce qui touche à la vie, de l'infiniment petit à l'infiniment grand serait régi par ces règles mathématiques. Ce serait valable pour la formation de n'importe quel organisme vivant, du plus complexe jusqu'aux êtres unicellulaires, et ce serait donc également valable pour la formation de l'univers (ils ont même expliqué la "ola" dans les stades par ce genre de modèle). Avant la formation de l'univers, il y aurait forcément une règle mathématique, ou un "code cosmologique" qui engendrait tout le reste, car l'univers n'a pas pu se former à partir de "rien"... Pour la comparaison avec le code génétique, ce serait en réalité le code génétique (comme tout le reste de la vie) qui "dérive" du code cosmologique...

Voilà quelques explications si ça peut vous éclairer :D

Modifié par Guybrush Threepwood

Partager ce message


Lien à poster

pour les matheux et les physiciens :unsure:

j'ai manké l'émission merdeeeeeeeeeeeee :D

pourtant avec 12 et 16 en maths et physique au bac j'aurais été au niveau :diable: quoi que justement je savais deja tout :unsure::blink:

Partager ce message


Lien à poster
E=m.c² ne s'applique pas dans ce cas c'est tout. Ca tu l'utilises dans le cas de la chute libre d'un objet par exemple. Enfin il me semble.

<{POST_SNAPBACK}>

E=mc² , c'est la formule d'Einstein pour calculer l'énergie interne d'un noyau radioactif... on multiplie la masse m du noyau par la célérité au carré (la célérité étant la vitesse de la lumière dans le vide)

Tu confonds avec l'énergie cinétique => E©=(1/2)m.v² ... la vitesse de l'objet en chute libre est inversement proportionnel à sa masse... enfin là je suis plus très sûr, ça fait longtemps que je ne fais plus de physique :diable:

Partager ce message


Lien à poster

et après on dit que les supporters sont des debiles profond connaissant 60 mots au max :diable:

Partager ce message


Lien à poster
et après on dit que les supporters sont des debiles profond connaissant 60 mots au max  :diable:

<{POST_SNAPBACK}>

60 mots sa commence a faire bp je sais pas si j'en connais autant :D

Partager ce message


Lien à poster

La formule E=mc² ne s'applique pas pour les corps de trés petite ou trés groose masse. C'est peut etre pour ça.

Des chercheurs ont meme montré que des corps de trés petite masse peuvent dépasser la vitesse de la lumière je crois.

Partager ce message


Lien à poster

je l'ai maté aussi......ça me fait tripper quand tu vois qu'ils calculent aprés la mort de la terre,aprés l'implosion du soleil qui va s'effondrer sur lui meme,ou se transformer en naine blanche..

Partager ce message


Lien à poster

Introduction : algorithmes génétiques

C'est en 1975que John Langton parle pour la première fois des algorithmes génétiques, une technique de programmation qui s'inspire du principe de l'évolution des espèces décrit par Darwin, mais ce n'est que récemment (vers le début des années 90) que cette technique arrive sur le devant de la scène, s'inscrivant un peu, avec les techniques liées à la vie artificielle d'une façon plus générale, comme une voie de renouvellement pour le génie logiciel et l'intelligence artificielle (certains préfereront parler d'informatique avancée). On ne s'étonne guère du succès de cette façon de programmer quand on sait que la simplicité de cette technique n'a d'égale que sa puissance. C'est en effet cette légèreté de mise en oeuvre qui fait tout le charme des algorithmes génétiques et qui donne cette impression rafraîchissante d'avoir insuflé un peu de vie et de créativité dans l'ordinateur. Ce seul aspect révolutionnera peut-être la façon que l'on a de voir les machines qui nous entourent.

Ce texte se propose juste, en attendant une couverture plus ambitieuse, de présenter le principe élémentaire qui est à la base de la programmation génétique.

Le principe de l'évolution

--------------------------------------------------------------------------------

Le principe de base est simple et génial : il s'inspire de la théorie de Darwin sur l'évolution des espèces qui explique comment depuis l'apparition de la vie les espèces ont su évoluer de façon innovante et souple dans le sens d'une meilleure adaptation à l'environnement et qui éclaire ce chemin vertigineux qui, commencé par d'ambitieux organismes unicellulaires, a su nous mener à la vie telle qu'on la connaît aujourd'hui dans toute sa diversité exotique et spectaculaire.

En permettant aux seuls individus bien adaptés à l'environnement de se reproduire, la nature assure la pérennité de leurs meilleures caractéristiques, lesquelles caractéristiques se recombinent entre elles (chaque enfant reçoit de bonnes caractéristiques à la fois de son père et de sa mère) pour former à chaque génération de nouveaux individus toujours mieux adaptés à leur environnement.

L'évolution des espèces

Considérons un environnement quelconque dans lequel vit une population primitive, i.e. peu adaptée à cet environnement. Bien sûr, quoique globalement inadaptée, cette population n'est pas uniforme : certains individus sont mieux armés que d'autres pour profiter des ressources offertes par environnement (nourritures, abris, etc.) et pour faire face aux dangers qui y rôdent (prédateurs, intempéries, etc.).

Ces individus mieux équipés ont par conséquent une probabilité de survie plus grande que leurs congénères et auront de fait d'autant plus de chances de pouvoir se reproduire.

En se reproduisant entre individus bien adaptés, ils vont transmettre à leurs enfants ces caractéristiques qui faisaient leur excellence.

La population qui résultera de cette reproduction sera donc globalement mieux adaptée à environnement que la précédente puisque la plupart des individus auront hérité de plusieurs (puisque chacun hérite à la fois de sa mère et de son père) des caractéristiques de l' "élite" de la génération précédente.

Et c'est ainsi, en recombinant à chaque génération les caractéristiques élémentaires de bonne adaptation et en saupoudrant le tout d'un peu de hasard, que la population va évoluer vers une adéquation toujours meilleure avec l'environnement.

Le codage de l'information

Le principe est très convaincant mais une question s'impose : comment cette transmission d'informations est-elle possible ? L'explication viendra plus tard avec la découverte de la génétique (Mendel 1822-1884) et de l'ADN (Griffith 1928, Avery, McLeod et McCarthy 1944). On se rend compte que toutes les informations nécessaires à la genèse d'un individu (son patrimoine génétique, tout ce qui dicte sa construction et qui décrit toutes ses caractéristiques) sont contenues dans les molécules d'ADN dont chaque cellule de l'organisme possède une copie. Le processus de reproduction fait se rencontrer deux cellules sexuelles (une du père une de la mère) qui voient leurs molécules d'ADN s'enchevêtrer, se croiser, ce qui donnera une cellule fille (futur individu) dont le patrimoine génétique sera un mélange des patrimoines des parents.

Applications aux algorithmes génétiques

--------------------------------------------------------------------------------

Les algorithmes génétiques vont s'inspirer directement de ces principes pour résoudre une grande variété de problèmes d'optimisation. Face à un problème pour lequel il existe pour ainsi dire une infinité de solutions, plutôt que d'essayer naïvement toutes les solutions une à une pour trouver la meilleure, on va explorer l'espace des solutions en se laissant guider par les principes décrits plus haut.

Plus concrètement :

Il faut d'abord définir un codage : établir une convention qui permette de décrire chaque solution possible sous la forme d'une chaîne de caractère (l'analogue de la molécule d'ADN).

Ensuite, il faut définir précisément une fonction d'adaptation qui pour chaque solution possible donnera une valeur reflétant sa qualité pour résoudre le problème posé : plus la valeur de la fonction est élevée, meilleure est la solution.

Ceci fait, on se dote d'un ensemble de solutions choisies au hasard : c'est la population de départ.

A l'aide de la fonction d'adaptation, on évalue chacune d'entre elle.

On s'attelle maintenant à la construction de la génération suivante. Pour commencer à construire cette nouvelle génération, il nous faut deux parents : on les prend parmi la population de départ en les choisissant avec une probabilité d'autant plus grande que leur adaptation était bonne : c'est la phase de sélection.

Partant de ces deux parents, on construit une descendance par croisement : on coupe les chaînes de caractères qui décrivent les parents en plusieurs morceaux dont la taille est tirée au hasard.

On construit alors toutes les recombinaisons possibles de ces morceaux : l'enfant sera construit morceau par morceau : le 1er morceau du fils sera soit le 1er morceau de la mère, soit le 1er morceau du père, son 2ème morceau, soit le 2ème morceau de la mère, soit le 2ème morceau du père, etc. On construit ainsi autant d'enfants que de recombinaisons possibles.

ex : avec deux morceaux :

Père : 1111000

Mère : 1001110

Fils 1 : 1111110

Fils 2 : 1001000

On fait se reproduire autant de couples de parents que nécessaire pour régénérer toute la population.

Pour terminer, on procède au hasard à quelques mutations : chaque caractère de chaque chaîne a une faible probabilité de voir sa valeur changée complètement au hasard. Cette procédure a pour objet de dynamiser l'exploration de l'espace des solutions et surtout d'éviter aux nouvelles générations de rester bloquées dans un minimum local de la fonction d'adaptation dont on ne pourrait pas sortir en ne faisant que recombiner les caractéristiques des générations précédentes.

On a bien construit une nouvelle génération qui a hérité des meilleures caractéristiques de la génération précédente (puisque les individus possédant ces caractéristiques se sont plus probablement reproduits que les autres) et qui les a recombinées pour proposer des solutions originales et probablement plus efficaces au problème. Il ne reste plus qu'à recommencer jusqu'à ce qu'on obtienne des solutions satisfaisantes au problème...

Partager ce message


Lien à poster

1. La naissance des automates cellulaires

Les automates cellulaires ont été inventés par Stanislaw Ulam (1909-1984) et John von Neumann (1903-1957) à la fin des années 40 au Los Alamos National Laboratory (Etats-Unis) ( cf. Photos en ANNEXE A).

Lidée de départ de von Neumann et dUlam

Von Neumann est indiscutablement un grand génie du XXe siècle, bien que ses travaux ne soient pas très connus du grand public. Le nombre de domaines auxquels il apporta des contributions décisives ne peut que laisser admiratif. Il fut un des pionniers dans la conception des ordinateurs, sa « Théorie des jeux » est un outil toujours utilisé par les décideurs dans les domaines économiques et militaires, il fit des avancées majeures en mécanique quantique et en physique nucléaire. Né à Budapest, en Hongrie, le 3 décembre 1903, il est souvent dépeint comme un génie précoce, capable de diviser mentalement deux nombres de huit chiffres. A lage de 20 ans, von Neumann publia une définition de nombres ordinaux qui est toujours utilisée de nos jours. A lâge de 25 ans, il découvrit que les états des systèmes quantiques pouvaient être représentés par des vecteurs dun espace abstrait de dimension infinie. Il émigra aux Etats-Unis en 1931 et devint professeur de mathématiques à luniversité de Princeton. Parallèlement à ses recherches fondamentales sur la logique mathématique, ses travaux de mathématiques allaient sorienter vers une voie plus appliquée et durant les années 30, il allait travailler sur des modèles idéalisés de confrontations entre acteurs rationnels et donner ainsi naissance à la théorie des jeux. Durant la deuxième guerre mondiale, von Neumann dirigea la conception des premiers ordinateurs destinés à larmée américaine. Il fut particulièrement intéressé par les capacités logiques potentielles des ordinateurs et sinspira grandement des travaux du mathématicien et logicien britannique Alan Turing. Parallèlement à ces recherches, il allait se consacrer à des études mathématiques, telles que la recherche de séquences dans pi, ou logiques, telles que létude des automates auto-reproducteurs. Von Neumann allait mourir le 8 Février 1957, des suites dun cancer probablement dû à des expositions à la radioactivité.

La partie de ses travaux qui nous intéresse ici est son étude des automates auto-reproducteurs. En 1948, von Neumann a proposé un article intitulé « Théorie générale et logique des automates » dans une conférence tenue à Pasadena, en Californie. En 1949, il donna une série de cours sur le thème : « Théorie et organisation des automates complexes ». Une des questions centrales de ce cours était de savoir sil était possible de concevoir une machine capable de sauto-reproduire. En effet, il est clair que les objets fabriqués par une machine sont généralement plus simples que la machine elle-même. Prenons lexemple dune usine de fabrication de bouteilles de soda, on ne contestera pas dans ce cas que la bouteille est plus simple que la machine qui la fabriquée. Même dans le cas dune usine de fabrication dordinateurs, loutillage utilisé est bien plus complexe que le produit fabriqué.

Von Neumann émit lidée quune machine capable de manipuler des composants de machine élémentaires pourrait résoudre ce problème. Dans sa première conception, lautomate devait puiser dans un réservoir de composants de machine et construire un automate similaire à lui-même, à la façon dont on construit un automate par un jeu de « Meccano ». Mais cela nécessitait que lautomate soit doté dun système de vision et de reconnaissance suffisamment élaboré pour pouvoir distinguer les différents éléments de machine. Cet automate aurait dû être en outre doté de capacités exceptionnelles pour pouvoir souder et manipuler des tubes à vide sans les abîmer. Ces exigences étaient tout simplement inconcevables étant donné létat des techniques dans les années 50.

La solution à ce problème vint dun collègue de von Neumann au laboratoire de Los Alamos : Stanislaw Ulam[7]. Elève de Banach (1892-1945), influencé par les lectures de Sierpinski (1882-1969) ; Ulam est lauteur dun problème simple non encore résolu à ce jour : « prenez un nombre, si ce nombre est pair divisez le par 2, sil est impair multipliez par trois et ajoutez un, vous obtenez une suite de nombres, toute suite finit-elle par converger vers le cycle 4/2/1 quel que soit le terme initial choisi ? » Il est notamment connu pour être linventeur de la méthode Monte-Carlo et pour ses travaux sur la fusion nucléaire. Ulam sintéressait aux « objets géométriques définis de façon récursive »[8] quil étudiait après les heures réglementaires de travail en utilisant les ordinateurs du laboratoire de Los Alamos. Ces objets provenaient de jeux aux règles simples dans lesquels on pouvait voir des figures [patterns] se développer, se reproduire, combattre pour une portion de territoire et mourir. Ces jeux se déroulaient dans un univers « cellulaire », composé dune matrice infinie où les cellules, régulièrement réparties, peuvent être dans un état passif ou un état actif. Les figures de cet univers étaient composées des cellules actives, et à tout moment, le devenir de chaque cellule était dicté par létat des cellules avoisinantes. Ulam saperçut que lanalyse de ces figures défiait le bon sens : elles semblaient évoluer dans un monde qui leur était propre avec des lois bien spécifiques. Il suggéra alors à von Neumann dutiliser un tel monde abstrait pour pallier les difficultés pratiques qui se posaient pour la construction de lautomate auto-reproducteur. Ce monde serait suffisamment complexe pour pouvoir simuler les opérations élémentaires des machines et en même temps construit de façon à ce que les lois de la physique qui gouvernent ce monde se réduisent à quelques règles simples. Lidée plut à von Neumann qui était habitué à voir les machines comme des circuits logiques[9], il adopta donc lunivers dUlam pour commencer à réfléchir à son automate [Poundstone85].

Le problème de lauto-reproduction

Un premier problème était résolu mais il restait à concevoir un mécanisme dauto-reproduction. Von Neumann aboutit à lidée quun automate auto-reproducteur devrait comporter une unité baptisée « constructeur universel » qui serait capable de fabriquer nimporte quelle machine (cellulaire) à partir dune description qui lui serait fournie. Dans le cas particulier où lon fournirait la description de constructeur universel au constructeur universel lui-même, il y aurait auto-reproduction. Le raisonnement semble simple à première vue mais il se pose un problème de logique : le système auto-reproducteur (SAR) est constitué du constructeur universel (CU) et de sa propre description (DESC). Or cette description ne peut être la description du constructeur universel seulement, elle doit être la description de tout le système, et donc être en particulier une description de la description. En équations, nous avons : SAR = CU + DESC ( SAR ), ce qui paraît a priori insoluble étant donné lexistence dune régression à linfini (lorsquon remplace SAR dans le terme de droite par le contenu de léquation).

Ce problème pouvait-il être résolu? Existait-il un moyen d « expliquer » à lautomate que la description ne devait pas sinclure elle-même ? Von Neumann sinspira des travaux de Turing pour trouver un remède. Nous devons en effet à Church et à Turing lidée selon laquelle tout calcul [Turing36], et plus généralement tout problème bien formalisé [Turing54] quel que soit sa complexité, peut être réduit à une séquence dopérations appelée « algorithme ». Ces opérations sont choisies dans un catalogue réduit et leur exécution peut être confiée à une seule machine précise appelée machine universelle. Selon la thèse dite de Church-Turing, cette machine posséderait la capacité (virtuelle) de résoudre tout calcul, aussi complexe soit-il. Nous nommerons cette propriété la « calculabilité universelle[10] ». Le fait que ces opérations élémentaires soient choisies dans un catalogue fini permet leur transcription dans lunivers cellulaire ou le nombre détats des cellules est aussi fini.

Le problème fut résolu par von Neumann en ajoutant une troisième unité : une machine universelle de Turing, le superviseur, devait orchestrer le processus. Lutilisation du superviseur évitait la régression à linfinie en distinguant deux phases :

(1) Lensemble ( constructeur universel + superviseur ), le « copieur-superviseur » réalise une copie de lui-même dans une région vide de lespace en lisant la description, cest la phase dinterprétation.

(2) La phase (1) étant terminée, le superviseur comprend quil ne faut plus que la description soit interprétée ; celle-ci est considérée comme un ensemble de données et recopiée littéralement pour rebâtir le système initial [Heudin98].

En 1952, la description de lautomate auto-reproductif était terminée et von Neumann proposait une version qui utilise 29 types de cellules différentes. Létat de chaque cellule au temps t était déterminé uniquement par létat des quatre cellules adjacentes et celui de la cellule centrale au temps t-1. Ce voisinage est dailleurs nommé voisinage de von Neumann en hommage à son inventeur. Néanmoins, même dans lunivers simplifié des automates cellulaires, lensemble ( constructeur universel + machine de Turing universelle + description du système ) était constitué de plus de 200 000 cellules ! Après cette première « victoire » et de façon assez surprenante, von Neumann allait délaisser létude des automates cellulaires pour satteler à dautres problèmes scientifiques et ses résultats concernant lauto-reproduction ne seront jamais publiés de son vivant. Il est possible que la trop grande complexité de son modèle lait déçu. En outre, la « physique » qui régissait ce monde artificiel possédait un défaut majeur : elle nétait pas réaliste puisquelle ne respectait pas les conditions de symétrie du monde physique. Cela se traduit mathématiquement par le fait que la fonction de transition f qui règle lévolution dune cellule en fonction de son voisinage nest pas invariante par rotation ou par réflexion (cf. III.1). Par ailleurs, cette trop grande complexité du modèle fit quil ne put jamais être testé sur un ordinateur, les capacités de calcul des premiers ordinateurs étant nettement insuffisantes à cette époque.

La première publication sur le sujet provient dUlam qui définit alors le concept dauto-réplication dune façon formelle [ulam 50] :

« Un champ dapplication intéressant pour des modèles qui sont constitués dun nombre infini déléments interagissant peut être trouvé dans les théories récentes des automates. Un modèle général, considéré par von Neumann et lauteur, serait comme suit : Etant donné un réseau infini de points, chacun possédant un nombre fini de connections à certains de ses voisins, chaque point a la possibilité de se trouver dans un nombre fini détats. Les états des voisins au temps tn induit létat du point au temps tn+1. Un des objectifs de la théorie est de prouver lexistence de sous-systèmes qui sont capables de se multiplier, cest-à-dire de créer dans le temps dautres systèmes identiques à eux-mêmes. »[11]

Ce nest quen 1966 que la publication du premier grand ouvrage consacré au problème de lauto-reproduction est enfin réalisée, par Arthur Burks, qui complète les travaux inachevés de von Neumann et publie Theory of self-reproducing automata [vonNeumann66]. Le nom d « automate cellulaire » est dailleurs une création de Burks. En 1968, le second ouvrage consacré aux AC paraît : il est publié par Codd sous le titre Cellular Automata, sous la forme dun manuel dune centaine de pages [Codd68]. Les résultats sont présentés de façon nettement plus concise que dans [vonNeumann66], ce qui va permettre aux étudiants de se familiariser avec le domaine. Les années 60 voient aussi la résolution des premiers problèmes mathématiques liés aux AC. Le problème dit de « synchronisation des fusiliers » a par exemple été inventé par Myhill en 1957, et publié pour la première fois par Moore en 1964 [Moore64]. Il consiste à trouver un automate cellulaire unidimensionnel, tel que, partant dune configuration où toutes les cellules sont dans létat de repos (cf. II.1) à lexception dune unique cellule, on arrive à une configuration où toutes les cellules sont dans un même état (état dit de feu), état qui nest jamais apparu avant. Le problème peut sexprimer de façon imagée comme suit :

« Comment synchroniser une ligne de fusilliers de façon à ce quils se mettent à tirer ensemble, alors que lordre donné par un général depuis lun des deux bords de lescadron met un certain temps à se propager ? » [Yunes93].

Pour reprendre le vocabulaire de Kuhn dans La structure des révolutions scientifiques [Kuhn70], on peut dire que lapparition dun manuel ainsi que la création de problèmes qui occupent une communauté est le signe que ce domaine détude devient un champ théorique digne de ce nom, autrement dit quun paradigme est en train de naître. Il est néanmoins trop tôt pour dire quil existe un nouveau domaine scientifique : les automates cellulaires restent à ce stade une branche particulière ce que les historiens des sciences nomment « la première cybernétique

Partager ce message


Lien à poster

2. Un nouvel axe de recherche : le Jeu de la Vie

Un univers à explorer

Dans le numéro dOctobre 1970 de Scientific American, Martin Gardner publie un article intitulé « Les combinaisons fantastiques du Jeu de la Vie de John Conway » [Gardner70]. Conway a inventé un automate cellulaire qui a la particularité suivante : des figures peuvent croître et atteindre une grande taille mais pourtant, on ne peut dire de façon évidente sil existe des figures qui vont croître à linfini. Cet automate cellulaire se nomme Game of Life ou Life en abrégé.

Les règles du Jeu de la Vie sont extrêmement simples. Les cellules peuvent se trouver dans deux états qui sont : vivant / mort, lespace cellulaire est composé de cellules qui se trouvent dans létat mort au départ, sauf pour un nombre fini dentre elles. Lévolution de chaque cellule est déterminée en fonction du nombre Nv de cellules vivantes se trouvant dans les huit cases adjacentes à une cellule. Les règles sont :

· Une cellule vivante meurt (devient vide) pour Nv = 1 : cela correspond à un état disolement de cellule.

· Une cellule vivante meurt pour Nv = 4 : cela correspond à un état de surpeuplement autour de la cellule.

· Une cellule morte peut devenir vivante pour Nv = 3 : cela correspond à une reproduction « trisexuée ».

Le Jeu de la Vie marque un tournant dans létude des automates cellulaires car contrairement aux modèles précédents où lon décidait des règles et du nombre détat dans un but bien précis (prouver la calculabilité universelle, la constructibilité universelle), on cherche désormais à trouver les propriétés des automates daprès leur règles de fonctionnement. Le travail des chercheurs sapparente alors à celui des physiciens qui étudient des phénomènes, préparent des expériences et essaient de découvrir de nouveaux objets. Néanmoins, il existe une différence de taille avec le travail des physiciens : lévolution des objets manipulés, bien que totalement déterminée par les fonctions de transition, est hautement imprévisible. On remarque ainsi quil ny a pas de correspondance apparente entre la taille dune configuration initiale et le temps quelle met pour se stabiliser. Par ailleurs, le simple fait dajouter ou denlever une cellule dans une configuration change son évolution de façon radicale. Comment, dans ces conditions, espérer parvenir à construire une expérience ?

Létude des propriétés de Life a démarré avec celle de la découverte des objets stables. Généralement, les chercheurs classent les objets selon leur forme de stabilité. Les objets les plus simples à étudier sont ceux qui restent identiques à eux-mêmes avec le temps, un bloc carré de quatre cellules par exemple. Viennent ensuite les objets qui dont lévolution est périodique, nommés oscillateurs. Loscillateur le plus simple est le clignotant ; il est constitué de trois cellules alignées, et possède une période 2. Une autre classe dobjets importants est celle des objets périodiques qui se translatent avec le temps. Le planeur est lexemple le plus simple et il apparaît de façon spontanée lors des simulations.

Petit à petit, les chercheurs ont procédé comme des naturalistes et ont découvert des figures stables de plus en plus complexes. Ces découvertes se font selon deux méthodes : la première consiste à initialiser lespace cellulaire de façon aléatoire et à observer les figures qui apparaissent de façon spontanée (cf. ANNEXE :grin:. La seconde méthode consiste à construire, par des procédés souvent très ingénieux, des figures périodiques qui éventuellement se translatent. Un grand concours -implicite - a débuté au début des années 70 pour la découverte de nouvelles figures stables. Les chercheurs ont rivalisé dastuce et ont fini par mettre à jour toute une faune exotique qui peuple lunivers du Jeu de la Vie. Des noms aussi évocateurs que « le mangeur, la navette, le crapaud, le phare ou le serpent » ont été donnés (et continuent dêtre données) aux figures stables découvertes. On peut dresser un parallèle avec ce qui se produit en astronomie, où les chercheurs rivalisent pour lobservation de nouveaux astres, avec à la clé la possibilité de nommer lastre du nom du découvreur.[12] Vu de lextérieur, cette course folle au plus complexe semblait futile aux autres scientifiques. Létude du Jeu de la Vie prit des proportions telles quen 1974, on pouvait lire dans les colonnes du magazine américain Time que « des heures de calcul représentant des millions de dollars avaient été gaspillées par la horde grandissante des fanatiques de ce jeu » [Time74].

Recherche scientifique ou simple passion ?

Ce jugement sévère était-il justifié ? Ces chercheurs étaient-ils des « fanatiques » ou à lopposé plutôt des « scientifiques » dont la discipline nétait pas encore reconnue ? La recherche des propriétés de Life peut-elle être qualifiée de « scientifique » ? Selon le scénario proposé par Kuhn, une discipline scientifique apporte des « énigmes » [puzzles] à la communauté scientifique concernée. Nous pouvons donc essayer destimer la scientificité de létude du Jeu de la Vie en étudiant les « énigmes » qui sont nées de létude du Jeu de la Vie.

Le premier problème fut posé par Conway lui-même qui, en 1970, conjectura quil existait des figures (ensembles de cellules vivantes) qui pouvaient croître de façon illimitée. Conway avait créé le Jeu de la Vie en espérant quune telle possibilité pourrait être réalisée ; néanmoins aucune preuve mathématique de la réalisation de la croissance illimitée ne pouvait être établie. Il fallait donc exhiber une figure dont lévolution soit totalement prévisible et dont la taille augmente de façon régulière. Gardner offrit un prix symbolique à celui qui arriverait à prouver ou à réfuter la conjecture de Conway avant la fin de lannée. Le prix fut remporté par William Gosper et cinq autres informaticiens du MIT qui réussirent à exhiber une figure, baptisée lance-planeur (« glider gun »), qui est un oscillateur à lévolution cyclique et qui a la propriété démettre un planeur toute les trente générations. Une telle découverte naurait rien dimpressionnant de nos jours mais il faut se souvenir quen 1970, nous sommes à laube de lère informatique et que les simulations dévolutions se mènent parfois à laide de pions de jeu de dames ou dOthello. Lexistence du « lance-planeurs » constituait la première résolution dune énigme liée au Jeu de la Vie : elle démontrait que la croissance illimitée était possible.

Un autre problème qui a occupé la communauté des chercheurs fut celui de la réversibilité. Un automate est dit être réversible sil ne se produit pas de perte dinformation au cours de lévolution de lautomate : chaque configuration possède donc un unique successeur (déterminisme de lAC) et un unique prédécesseur. Il est clair que lon peut déduire facilement des règles du Jeu de la Vie que lon nest pas en présence dun automate réversible puisque des configurations différentes peuvent avoir un même successeur. Par contre, une propriété qui nétait pas évidente était lexistence de configurations qui nadmettent aucun état qui puisse les engendrer. De telles configurations sont appelées « jardins dEden » car elles ne peuvent être que des états initiaux ; on peut donc dire de façon imagée « quelles ont tout simplement été crées ». La question du jardin dEden est posée pour la première fois par Moore en 1962 [Moore62], concernant les automates auto-reproducteurs. Lexistence de jardins dEden na rien dévident, car on ne voit pas a priori ce qui empêcherait une configuration donnée davoir un prédécesseur. En 1970, le mathématicien Alvy Ray Smith démontra lexistence de jardins dEden dans Life, puis un exemple fut donné par Banks. La configuration quil propose tient dans un rectangle de 9 par 33 cellules, cf. [Heudin98, p.62], [Poundstone85, p.50], elle est donc relativement complexe ; la démonstration elle-même est assez sophistiquée, ce qui se comprend aisément puisquil sagit de montrer quaucune configuration de Life ne peut engendrer le candidat au titre de jardin dEden. Le Jeu de la Vie donne donc naissance à des problèmes qui font certes appel à linformatique mais dont la résolution requiert des techniques purement mathématiques. Dautre part, la découverte de figures stables de plus en plus élaborées semblait montrer que malgré limpossibilité de prévoir lévolution de la majorité des configurations, il existait néanmoins un certain ordre dans cet univers.

La calculabilité et la constructibilité universelle dans le Jeu de la Vie

Jusquà quel point pouvait-on maîtriser lunivers de Life ? La question fondamentale était de déterminer si Life possédait les capacités de calculabilité et constructibilité universelle. Nous avons vu (cf. I.1.) que Von Neumann avait prouvé quun automate cellulaire pouvait servir de calculateur universel en utilisant un modèle qui employait 29 états élémentaires et dont les « lois de la physique » ne respectaient pas les conditions de symétries élémentaires telles que linvariance par rotation et linvariance par réflexion. Codd dans [Codd68] a fait un pas de plus vers la simplification en montrant que la condition de calculabilité universelle pouvait être réalisée par un automate cellulaire à 8 états élémentaires avec un voisinage de cinq cellules (4+1) et des règles qui respectaient linvariance par rotation mais non linvariance par réflexion. Jusquoù pouvait-on continuer dans cette recherche de simplicité ? Était-il possible que Life, qui était bien plus simple dans son nombre détats et dans ses règles puisse avoir la même puissance de calcul et de construction ? Le mystère restera entier jusquen 1982 où Conway publiera, avec dautres chercheurs, une preuve détaillée de la possibilité de simuler nimporte quel calcul à laide du Jeu de la Vie [berlekamp&al.82].

Dans la construction de Conway, lunité de base qui sert à la circulation de linformation, léquivalent dun bit en théorie de linformation, est le planeur. Chaque nombre peut être codé selon un faisceau de planeurs généré par un lance-planeurs, et on montre que toutes les portes logiques telles que ET, OU, NON ainsi que les propriétés de mémoire en lecture / écriture peuvent être réalisées à laide dinteractions entre figures stables connues. Conway a aussi montré que lon pouvait concevoir un constructeur universel dans le Jeu de la Vie. Le lecteur qui souhaiterait avoir un exposé simplifié mais qui reprend chaque étape de la démonstration de Conway peut se reporter à [Poundstone85, chap. 12]. Les constructions utilisées dans la démonstration pourront sembler étranges, complexes, voire tortueuses aux personnes habituées aux mathématiques « classiques », mais si lon sy intéresse en détail on retrouve la même élégance, la même quête de lessentiel que dans une démonstration de mathématiques. Le Jeu de la Vie allait donc apporter la preuve que la condition de calculabilité universelle peut être réalisée par un automate ayant 2 états, un voisinage de 9 cellules, et aux règles invariantes par rotation et par réflexion. A ce jour, des automates cellulaires réalisant la condition de calculabilité et de constructibilité universelle, Life est lautomate le plus simple que lon connaisse. La démonstration de Conway allait quasiment clore le chapitre concernant le Jeu de la Vie, en effet la possibilité même de la démonstration semblait indiquer que lon maîtrisait « suffisamment » la physique de ce monde. Il était donc temps dexplorer de nouveaux mondes

Partager ce message


Lien à poster

Créer un compte ou se connecter pour commenter

Vous devez être membre afin de pouvoir déposer un commentaire

Créer un compte

Créez un compte sur notre communauté. C’est facile !

Créer un nouveau compte

Se connecter

Vous avez déjà un compte ? Connectez-vous ici.

Connectez-vous maintenant

×