logo admiroutes Les automates intelligents
robotique, vie artificielle, réalité virtuelle


information, réflexion, discussion
logo automate © Anne Bedel
Jean-Paul Baquiast Jean-Paul.Baquiast@wanadoo.fr
Christophe Jacquemin christophe.jacquemin@admiroutes.asso.fr

N° 32
Retour au sommaire
 
Dossier Stephen Wolfram
Les programmes computationnels simples selon Wolfram
par Jean-Paul Baquiast - 3 juin 2002
provisoire          

A new Kind of ScienceNous poursuivons ici la lecture commentée du livre "A New Kind of Science", en abordant la question très controversée du rôle des Automates cellulaires dans la démarche scientifique de Stephen Wolfram

Pour une initiation aux Automates cellulaires et à la vie artificielle, rappelons le travail réalisé par Jean-Philippe Rennard http://www.rennard.org/alife/
Voir aussi notre interview http://www.automatesintelligents.com/interviews/2001/mar/j_rennard.html, ainsi que les extraits de son prochain livre : http://www.automatesintelligents.com/biblionet/2002/avr/rennard.html
Sur les problèmes de la computation dans l'univers, on pourra consulter l'article de Seth Lloyd du MIT : "Computational Capacity of the Universe" (abstract : http://link.aps.org/abstract/PRL/v88/e237901) , pau le 10 juin 2002 dans Physical Review Letters. Pour plus d'explications : http://focus.aps.org/v9/st27.html
Voir aussi son précédent article : "Computational capacity of the Universe " (daté du 24 octobre 2001) sur http://arxiv.org/PS_cache/quant-ph/pdf/0110/0110141.pdf (17 pages).

Les programmes simples

Les commentateurs pressés ont reproché à Stephen Wolfram d'appuyer toutes ses démonstrations sur des exemples tirés des Automates Cellulaires (AC). Ils avaient alors beau jeu de démontrer que ceux-ci représentent une catégorie trop étroite de systèmes informatiques, ne lui permettant pas de remettre en cause les pratiques de la science traditionnelle dont la modélisation fait généralement appel aux mathématiques classiques.

Mais en fait, S. Wolfram ne mentionne les AC que comme une catégorie particulière de ce qu'il appelle des programmes simples. La rigueur intellectuelle oblige donc à bien lire son livre afin d'apprécier ce qu'il entend par ce terme. L'auteur détaille cet aspect dans les chapitres 2 à 6 du livre, qui ne sont pas d'une lecture particulièrement facile, mais incontournables. Nous nous bornerons ici à en présenter les grandes lignes, invitant le lecteur à se reporter à l'original.

Aux mathématiques et aux programmes informatiques reposant sur la mise en œuvre d'équations ou autres formules mathématiques, Wolfram oppose les programmes simples - "simple programs" - lesquels comportent en premier lieu les AC (mais ne se limitent pas à ceux-ci). Plus précisément, nous pourrions appeler ces programmes "programmes computationnels simples" (on pourrait aussi parler d'algorithmes simples), c'est-à-dire des programmes susceptibles de tourner sur ordinateur à partir de règles ou instructions aussi simples que possible. La notion de simplicité est évidemment empirique. Un peu dans l'esprit du rasoir d'Occam, nous dirions que pour être simple, entre deux séries d'instructions visant le même objectif, il faudra préférer celle qui comportera le plus petit nombre d'opérations logiques ou lignes de programme.
Ce point est essentiel. On sait que la nature, sans utiliser d'ordinateurs, met en œuvre continuellement des procédures computationnelles ou algorithmiques multiples, fonctionnant sur des supports variés (atomes, molécules, gènes, neurones, etc.). Dans la suite du livre - et dans tous les cas selon lui - l'auteur nous montrera comment on peut faire apparaître, lorqu'on essaye de simuler de telles procédures, le fait qu'elles utilisent des algorithmes simples, sinon élémentaires, semblables à ceux détaillés qu'il détaille dans les chapitre 2 à 6 de ce livre.

Chapitre 2. L'expérience cruciale (The crucial experiment)

Ce chapitre nous indique tout d'abord comment l'auteur a découvert (un peu par inadvertance mais certainement de façon inévitable du fait de sa culture informatique) que les AC pouvaient générer des comportements complexes, ou partiellement complexes, à partir de programmes simples, pou lui universels.
C'est l'AC appliquant la règle 90 qui lui a fait apparaître les premières complexités sous forme de fractales ou séquences se reproduisant à l'identique (self-similar) incluses (nested) dans le développement du système. Beaucoup plus surprenant sera l'AC appliquant la règle 30 : il présente des structures irrégulières que l'auteur qualifie de complexes ou désordonnées (random, n'obéissant à aucune loi perceptible), qui se développent au fur et à mesure que tourne le système, après plusieurs millions de pas. Encore plus complexe et imprévisible : l'AC règle 110. Celui-ci présente un mélange de structures régulières et au hasard, dont les unes se répètent et les autres non.

Stephen Wolfram justifie ensuite la découverte qu'il a faite, et l'importance qu'il y attache. Celle-ci, rappelons-le, concerne le fait que des programmes simples peuvent générer du complexe, du hasard et donc de l'imprévisible. Pour le faire apparaître, il lui a fallu faire tourner longuement les AC, puisque ces caractères ne se révèlent qu'après des centaines, sinon des milliers, ou même des millions de pas. Comme personne avant lui n'imaginait cela possible, personne ne l'avait fait. Jusqu'alors l'informatique était considérée comme devant répondre à des cahiers des charges précis, en éliminant toute incertitude. Ces objectifs étant généralement complexes, le programmeur pensait indispensable de doter le système informatique de règles tout aussi complexes, en exploitant le plus souvent des équations mathématiques. Lorsque ces systèmes révélaient à l'usage, de façon qui est vite apparue inévitable, des bugs ou défauts, ces derniers ont été éliminés du mieux possible, au lieu de servir de tremplin pour découvrir d'éventuelles lois cachées du système.

D'une façon générale, il n'était venu à personne l'idée de faire tourner un programme par simple curiosité. Or la nature, nous dit Wolfram, fait tout le contraire. Comme elle ne poursuit pas de finalité, les systèmes évolutifs se déroulent jusqu'au bout de leurs potentiels. Ainsi il peuvent révéler des complexités inattendues. Stephen Wolfram était dans une position unique, nous dit-il (il ne se vante pas, puisque effectivement nul ne l'avait fait avant lui) pour réaliser la synthèse entre la recherche scientifique, qu'il connaissait, et le maniement pratique des ordinateurs, qu'il possédait tout autant.

Wolfram n'ignore pas que de nombreux AC ont été expérimentés dans le cadre des débuts de l'Intelligence Artificielle, dans les années 1970 (et même avant, par exemple, le fameux Jeu de la Vie , ou Game of Life, AC à deux dimensions inventé par Conway au milieu des années 60).
Mais, contrairement à Stephen Wolfram, leurs promoteurs n'avaient pas réalisé que des programmes simples pouvaient générer la complexité.

Chapitre 3. Le monde des programmes simples (The world of simple programs)

Le titre de ce chapitre répond bien à l'objection selon laquelle on ne peut fonder une nouvelle science sur les seuls AC, comme l'auteur prétend le faire.
Ainsi, pour Stephen Wolfram, les AC ne sont qu'une catégorie parmi de nombreuses autres des programmes computationnels simples sur lesquels il nous propose de fonder sa nouvelle science. Il est vrai que ces différentes catégories de programmes simples ne se distinguent pas par des résultats très différents. C'est d'ailleurs cette constatation qui le conduit à postuler que ces programmes révèlent des constantes de la nature. Il montrera dans la suite du livre que les systèmes naturels répondent aux mêmes règles.

Aujourd'hui, nous dit-il, existe dans l'informatique une grande quantité de programmes simples. On peut d'ailleurs penser que le programmeur inventif pourra en imaginer d'autres. Les plus connus et finalement les plus démonstratifs sont les AC. Ceux-ci à eux seuls sont très nombreux car on peut toujours en faire apparaître davantage en changeant simplement de façon infime les règles qui les construisent.
Dans le domaine des AC en une dimension (chaque pas actualisant une ligne), utilisant 2 couleurs, on peut identifier 255 types de choix possibles. Certaines des règles ainsi recensées ne mènent à rien de significatif ou même avortent dès le départ, l'AC devenant monocouleur. D'autres aboutissent à des structures répétitives, d'autres à des structures incluant des fractales. Les structures peuvent se répéter à l'identique ou, au contraire, se développer en taille (pour 1/3 des catégories).
16 règles enfin produisent de l'aléatoire (random) dont 10 le font indiscutablement selon 3 solutions différentes, l'aléatoire et le structuré se partageant l'espace du système selon des figures spécifiques.

Tout en restant simple, on peut aussi compliquer les règles de construction des AC. Le nombre des catégories peut alors s'accroître considérablement. Le chapitre examine alors des AC à 3 couleurs (blanc, gris et noir). Si on veut modéliser des systèmes de la nature comportant tels caractères spécifiques mal rendus avec 2 couleurs, la formule est ici plus commode. Mais le point important est que si l'on complexifie un peu les règles, le comportement d'ensemble de l'AC ne sera pas finalement très différent : il ne créera pas globalement plus de complexité qu'un AC aux règles plus simples. La marche vers la complexité s'y arrêtera aussitôt.

Nous ne reprendrons pas ici l'inventaire que fait l'auteur du monde des programmes simples, qui ne sont plus des AC proprement dits, mais qui formellement donnent des résultats très comparables. Il cite les automates mobiles (seule une cellule "active" est mise à jour à chaque pas, au lieu de toutes les cellules dans un AC) ; les machines de Turing (dont la cellule active ou "tête" peut prendre différents états) ; les systèmes à substitution (Substitution Systems) ; les systèmes à affichage de séquence (Tag Systèms); les machines à compteurs, analogues aux compteurs des ordinateurs (Register Machines) ; les systèmes symboliques (traitant des expressions mathématiques (Symbolic Systems).

Là encore, à travers tous ces systèmes à règles simples, les mêmes conclusions significatives se font jour. Ces systèmes se comportent globalement de façon très voisine quand on les fait tourner sur ordinateur le temps suffisant. L'ordre des éléments ne modifie pas leurs comportements. Pour un certain nombre de ces programmes, mais pas pour tous, la complexité apparaît sans que cela soit explicable à partir des règles, ni donc prévisible. Une fois atteint un certain seuil, la complexité n'augmente plus. Ce seuil où apparaît la complexité est souvent bas, c'est-à-dire qu'il est parfois atteint à partir d'un nombre limité de pas. L'augmentation de la complexité des règles ne modifie pas la complexité des résultats. Lorsque la complexité n'apparaît pas, on retrouve partout des motifs répétitifs et des fractals.

Finalement, il apparaît que dans un grand nombre de systèmes différents, les mêmes lois générales se révèlent à l'œuvre. De là il est légitime de suspecter que se révèlent ainsi des caractéristiques universelles, que l'on devrait retrouver dans tous les systèmes naturels.

Le lecteur pourra cependant constater que, parvenu au terme des trois premiers chapitres, des concepts cruciaux comme ceux de complexité, hasard (randomness), prédictabilité ont été évoqués mais n'ont pas été définis. Nous verrons en progressant dans le livre que l'auteur s'efforcera d'apporter dans les chapitres suivants les précisions qui nous sont nécessaires.

Chapitres 4 à 6. Les systèmes à base de nombre et autres systèmes

Dans les trois chapitres suivants, Stephen Wolfram étudie un grand nombre de systèmes différents, utilisant tous des règles simples, auxquels il a consacré des milliers (sinon plus) d'heures de machine, en produisant des kilomètres d'écrans. Nous ne pouvons ici détailler cette somme, qui n'intéressera que les spécialistes. Notons cependant que les programmes examinés couvrent globalement tout ce qui devrait être nécessaire pour identifier, dans la suite du livre, les systèmes opérant dans la nature. Nous sommes donc loin des AC à une dimension présentés par la critique comme "l'outil essentiel de compréhension du monde".

Voici une liste résumée des systèmes examinés par l'auteur, en signalant chaque fois que nécessaire certains résultats significatifs:

Les systèmes à base de nombres
Ceux-ci ont été traditionnellement et depuis longtemps étudié par les mathématiciens. Même simples, et s'il s'avère que ces systèmes génèrent de la complexité au hasard, les mathématiciens ne s'y intéressaient pas fondamentalement. De plus, traitant des nombres considérés comme des objets (exprimés usuellement en base 10 et non comme des séquences de bits en base 2), ne disposant pas non plus d'ordinateurs, les mathématiciens ne pouvaient explorer très loin les séries numériques. Même dans les cas où certains calculs furent prolongés le plus loin possible (les nombres premiers ou les décimales de pi), ils ne purent faire apparaître de régularités. Il n'en tirèrent pas pour autant de conclusions relatives à la notion de complexité et aux conditions de son apparition.

- Les fonctions mathématiques. La plupart sont simples et répétitives mais certaines, en très petit nombre et peu utilisées dans la modélisation des systèmes naturels, génèrent du désordre.

- "Iterated maps" : il s'agit de modifier un nombre compris entre 0 et 1 par mise en œuvre répétitive d'une règle fixe ou "map". Selon les règles choisies, l'itération produit ou non de la complexité. Le point intéressant est que des résultats très différents peuvent être obtenus à partir de modifications infimes de la règle (une différence d'1 milliard de milliard !). On a là un exemple de chaos avec sensibilité aux données initiales. Cela n'avait pu être découvert par les mathématiciens traditionnels qui utilisaient des nombres décimaux et non des nombres binaires. Mais ce phénomène à lui seul ne peut expliquer la complexité au hasard dans tous les cas.

- Les AC continus : ils permettent d'étudier les systèmes qui ne se présentent pas comme constitués d'éléments variant de façon discrète. Ceci répond à l'objection (fondée ou non) que les systèmes naturels évoluent de façon continue plutôt que pas à pas. Les AC continus à 3 couleurs reposent sur l'utilisation de cellules affichant toutes les nuances de gris entre le noir et le blanc. Or il se trouve que les AC continus présentent les mêmes caractéristiques que les AC à cellules discrètes, ce qui montre que l'évolution vers la complexité au hasard ne découle pas du caractère discret des éléments des systèmes. Mais cela montre aussi que la discrétion ou la continuité ne sont pas des éléments fortement discriminants quant aux modalités d'évolution des systèmes.

- Les Equations aux Dérivés Partielles (EDP): celles-ci sont indispensables aux mathématiciens et physiciens pour représenter l'état d'un point variant selon une fonction donnée dans l'espace et le temps. Selon S. Wolfram, elles n'auraient pas été nécessaires si les scientifiques avaient disposé de la technologie computationnelle qu'il emploie. Les EDP existantes (par exemple équation de diffusion, équation d'onde, équation du soliton...) font apparaître des comportements simples. L'auteur en a trouvé quelques autres dont le comportement se révèle finalement complexe et désordonné.

Il résulte de ces quelques exemples que l'on peut faire apparaître la complexité dans l'évolution des systèmes continus de la même façon que dans celle des systèmes à éléments discrets, mais plus difficilement. Il faut en effet analyser l'équation et savoir exactement ce que l'on cherche. Cependant, d'une façon générale, les systèmes continus montrent les mêmes caractères que les systèmes discrets.

Les systèmes à deux dimensions et plus

- Les AC
Les AC à deux dimensions se développent par ligne et colonne ; ceux à 3 dimensions utilisent aussi la hauteur. On retrouve alors des organisations proches de celles de la nature, par exemple les cristaux de neige. Les AC à 2 ou 3 dimensions ne montrent pas de différences notables avec les AC à une dimension. On retrouve les mêmes régularités, les mêmes fractales et les mêmes complexités au hasard, différentes selon les systèmes et la durée consacrée à leur développement.

- Les machines de Turing peuvent également être étendues au fonctionnement en deux dimensions, la tête pouvant se mouvoir en haut et en bas comme à droite et à gauche. Là encore, ces dernières ne se comportent pas de façon particulièrement significative.

- Les systèmes en réseau.
Il s'agit d'une catégorie différente de systèmes, composés de nœuds reliés par des connections. Ce n'est plus la disposition des nœuds dans l'espace géométrique qui les définit, mais le nombre et la nature des connections de nœuds à nœuds. On peut construire des réseaux en plusieurs dimensions, avec un nombre différent de nœuds et de connections. Différents modes d'évolution sont possibles, selon des règles plus ou moins simples. Les mêmes logiques évolutives que précédemment se retrouvent à l'expérience, lors du développement de réseaux construits avec des règles simples.

On pourrait penser que l'étude des réseaux devrait être poussée plus loin par l'auteur, compte-tenu de ce que l'on peut juger de leurs rôles dans les systèmes naturels. Ce sera là un point à préciser.

- Les systèmes à états multiples (multiways)
Ils se caractérisent par le fait qu'ils peuvent prendre plusieurs états différents à chaque pas. Leurs règles définissent en général les remplacements par blocs d'éléments, qui sont conservés dans le développement du système.

- Les systèmes par contraintes.
Les modèles utilisant de tels systèmes sont fréquents dans les sciences traditionnelles. Au lieu d'évoluer en appliquant des règles explicites, ils doivent satisfaire à des contraintes établies à l'avance. L'expérience montre qu'ils disposent de peu de liberté. Généralement une seule solution répond aux contraintes d'un système donné. Cependant on peut faire apparaître avec beaucoup de difficultés des cas générateurs de complexité.

Il faut se demander si l'évolution par contraintes est plus répandue ou moins répandue, dans la nature, que celle sous commandes d'algorithmes simples. Ace stade de son livre, Stephen Wolfram ne s'est pas posé la question.

Le désordre dans les conditions initiales

Les systèmes examinés jusqu'ici, dans les cas les plus simples, se développaient à partir d'une solution initiale ordonnée, une seule cellule noire ou blanche par exemple, pour les AC en une dimension. Que se passe-t-il lorsque l'on introduit du désordre dans les conditions de départ ? La façon la plus simple de le faire est d'organiser l'initialisation du système à partir d'une ligne de cellules réparties au hasard entre le blanc et le noir. L'introduction du désordre est intéressante car elle permet de répondre aux conditions supposées fréquentes dans la nature.

On pourrait penser qu'une initialisation au hasard ne permettrait pas l'apparition de systèmes ordonnés. Or c'est tout le contraire qui se produit. Dans la plupart des cas, les systèmes s'ordonnent très vite, en produisant des comportements qui ne sont pas désordonnés. Cependant, comme dans les exemples précédents, ceci n'est pas universel. Il apparaît des cas où des systèmes initialisés au hasard restent désordonnés, ou présentent un mélange d'ordre et de désordre différent dans chaque cas.

L'auteur classe, d'abord par une simple observation visuelle, de très nombreux cas de systèmes initialement désordonnés. Il les a réparties en 4 catégories principales, jouant un peu le rôle des espèces dans le monde biologique. Les deux premières manifestent des comportements ordonnés. La 3e et la 4e mêlent les comportements ordonnés et les comportements désordonnés, de façon plus systématique dans la 4e. Les limites entre classes, comme dans la biologie, ne sont cependant pas définies avec précision. Le Jeu de la Vie est un AC en deux dimensions qui entre dans la 4e catégorie.

Selon leur catégorie, les systèmes ont une sensibilité aux données initiales très différente.

oOo

Nous voici armés pour examiner, pour la suite du dossier, dans les prochains numéros de notre revue, la façon dont Stephen Wolfram, avec ANKS, se propose de retrouver ces différents systèmes à l'œuvre dans la nature. Ce sera, on le devine, un exercice particulièrement stimulant pour l'esprit.


Retour Accueil dossier


Retour au sommaire