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.
- ceux de la classe 1 y
sont insensibles, ceux de la classe 2 enregistrent des changements mais ceux-ci
restent localisés. Les systèmes de la classe 3 peuvent être
modifiés, y compris de façon complète. Cette catégorie
de systèmes dispose ainsi d'une capacité à transmettre
à longue portée l'information de changement découlant
d'une modification des données initiales. Les systèmes de la
classe 4 enregistrent des changements qui se propagent mais de façon
sporadique en restant limités à certains éléments
du système.
- Les systèmes de
classe 2 de petite taille (quelques éléments, discrets) manifestent
un comportement systématiquement répétitif, ne pouvant
répercuter à longue portée les changements dans les conditions
initiales.
- Dans les systèmes
de classe 3 et surtout de classe 4, il est intéressant d'étudier
en détail les confrontations entre ordre et désordre qui s'y
produisent. De nombreuses règles peuvent être identifiées,
par exemple l'apparition d'attracteurs. D'une façon générale,
les systèmes de classe 4 présentent la caractéristique
de pouvoir imiter les comportements de tous les autres, s'ils partent de conditions
initiales appropriées. Leurs comportements peuvent être extrêmement
divers et complexes. L'exemple le plus parlant de cette propriété
est l'AC de la règle dite 110. Mais nous renverrons à l'ouvrage,
pour le détail de toutes les analyses possibles concernant cette dernière
catégorie de système.
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 Wolfram
Automates
Intelligents s'enrichit du 
Dossier 
Nous
poursuivons ici la lecture commentée du livre 
