Archives Billets/Articles Un big Brother mondial de 500 millions de dollars Les élections françaises et les enjeux du spatial Chine : mauvais passage ou difficultés durables ? Tous les articles

15 septembre 2004
par Bernard François Karlber@aol.com

Les limites des mathématiques
Analyse des fondements des mathématiques et éclaircissement du théorème d'incomplétude de Gödel
(sur A New Kind of Science, de Stephen Wolfram)

Nous avons reçu ce nouvel article de Bernard François qui, rappelons-le, a traduit pour lui-même en français (et pour mieux l'expliquer à son fils ) l'ouvrage de Stephen Wolfram "A New Kind of Science" [voir notre dossier initié en 2002].
Bernard François est aujourd'hui en pourparlers avec l'équipe de Stephen Wolfram pour une éventuelle édition du livre en Français.
Lire l'article au format pdf
Voir également son précédent article sur Le hasard intrinsèque

Automates Intelligents

La question qu'on peut se poser en lisant la préface de A New Kind of Science (ANKS) de Stephen Wolfram, c'est comment en tant que créateur et diffuseur d'un des plus grands logiciels de mathématiques symboliques Mathematica, Wolfram a pu écrire que celles-ci ont des limites très étroites et qu'elles sont vouées à être remplacées dans le futur par le formalisme puissant à base d'automates cellulaires qu'il a commencé à proposer dans son livre. J'ai traduit cet ouvrage notamment pour être capable de lire et comprendre la plus volumineuse section du dernier chapitre intitulée "Implications pour les mathématiques et leurs fondements". Je vais essayer ici d'exposer les grandes lignes de son argumentaire et des expérimentations qui le soutiennent.

Disons tout d'abord un mot du style de Wolfram, pour ne pas se braquer d'entrée sur cette question si sensible de l'hégémonie des mathématiques dans notre imaginaire scientifique. Quand on s'attaque à une idéologie dominante en parlant de la "remplacer", des résistances réflexes se lèvent immédiatement, ceci lié directement à l'état de domination plus ou moins complet dans lequel on peut être. De plus selon Wolfram, il y a un problème de clarté incompatible avec le style habituel de la littérature scientifique quand on s'attaque à de tels sujets. Et vu l'importance du blocage dans lequel les mathématiques nous maintiennent, l'auteur a pris le risque de paraître provocateur, et j'ai tenté de respecter son point de vue.
Le style habituellement employé dans la littérature scientifique est discret et prudent, et je l'ai utilisé dans le passé avec dévotion. Mais j'ai découvert à un certain moment que les résultats les plus saillants étaient souvent incompréhensibles s'ils étaient présentés de cette façon. Pour faire comprendre qu'une chose est réellement importante, il est très difficile de manier ce style. Donc en écrivant ce livre, j'ai choisi de signaler sans détours l'importance que je crois associée à mes différents résultats. J'aurais peut-être pu éviter certaines critiques en montrant plus de modestie, mais cela aurait nuit grandement à la clarté (extrait tiré des notes de l'ANKS).

* * * * * * * * * * * * * * * * *

Le long développement sur les mathématiques se situe dans le dernier chapitre qui porte le nom de "Principe d'équivalence computationnelle". Ce principe est un des outils nécessaire pour décoder le raisonnement de Wolfram. Il vient en déduction de toute une série d'expériences décrites auparavant dans le livre et basées sur le comportement des automates cellulaires. Les plus simples des automates cellulaires sont des systèmes d'accumulation de cellules à deux couleurs possibles, mises à jour selon des règles tenant compte des couleurs initiales de la cellule et des deux voisines immédiates. Dans ce modèle très simple d'automate, comme il n'y a que trois cellules impliquées dans les mises à jour, il n'y a que huit situations possibles : 4 cas où la cellule centrale est blanche, 4 cas où elle est noire. Le détail de ces 4 cas dépendant des états des cellules voisines : la cellule centrale cernée par les blanches, cernée par les noires, blanche à droite et noire à gauche, et le contraire. Ces 8 situations peuvent donner chacune des nouvelles cellules centrales ou blanches ou noires. Ce qui donnent 2⁸ ou 256 règles possibles pour ce montage-là d'automates cellulaires.

En explorant systématiquement ces 256 règles presque par hasard, sans penser trouver quoi que ce soit d'exceptionnel, Wolfram s'est retrouvé devant des dessins étranges représentant les comportements de ces automates. Et il les a classés selon quatre catégories : répétitifs, nidifiants (ou fractals), aléatoires, et "à structures localisées". Déjà dans cette classification, les mathématiques étaient devenues inopérantes. On peut écrire une équation décrivant la première classe, mais déjà la seconde classe des fractales peut poser des problèmes. La troisième classe aléatoire sort du champ de pilotage des mathématiques, notamment dans la définition récente de l'aléatoire selon laquelle toute séquence aléatoire est incompressible. Alors que ces automates aléatoires sont le simple fruit d'une règle résumée dans 8 cas. Et même avec des critères plus opérationnels, on ne peut prédire leur comportement, on est obligé de dérouler l'automate pour connaître son comportement. Celui-ci est résistant à toute algorithmie ou raccourci. Le quatrième cas des automates à structures localisées est encore plus inaccessible au formalisme mathématique et à la mise en équation. Et pourtant c'est l'image de la plupart des phénomènes complexes qui nous entourent.

Ces automates de classe 4 à structures localisées avaient déjà été repérés avec le Jeu de la Vie il y a quelques années, mais aucune des conséquences que leur existence entraîne n'avaient été tirées.

Comment penser un seul instant que ces dessins puissent remplacer les mathématiques ? Il suffit pour le moment de juste considérer que les mathématiques ne peuvent pas les manipuler, et qu'elles ne les tiennent pas dans leur champ. Par contre eux, les automates, peuvent modéliser les mathématiques et les résultats de ces modélisations sont loin d'être sans conséquences sur les jugements qu'on peut avoir sur les fondements mêmes des mathématiques. Mais comment modéliser les mathématiques ?

Quand Wolfram est tombé sur ces premiers automates, il a voulu savoir si les propriétés étranges de leurs comportements étaient liées à la forme particulière des automates cellulaires 'classiques' à deux couleurs. Et il a développé tout un bestiaire de systèmes possibles, d'abord pour isoler les caractères de ces premiers automates selon le bon réflexe de tout scientifique essayant de découper en morceaux pour voir qui est responsable de quoi. Et comme il retrouvait à chaque fois ces 4 classes (répétitives, nidifiantes, aléatoires et à structures localisées) dans les systèmes à substitutions, systèmes tags, machines de Turing, etc., utilisant telle ou telle caractéristique des premiers automates cellulaires, il a commencé à construire d'autres automates variés pour tester plus librement la généralisation de ces comportements. Les automates continus, ou à plusieurs couleurs, ou mobilisant plus de cellules voisines, ou les systèmes en réseaux,etc., ont confirmé qu'il était sur la piste de nouvelles lois générales.
Notamment une de ces nouvelles lois concerne l'existence d'un seuil au-delà duquel tous ces systèmes peuvent s'émuler entre eux. A partir du moment ou l'un de ces systèmes est capable d'atteindre un certain seuil de complexité relativement bas, il peut simuler le comportement de n'importe quel autre système ayant lui aussi atteint ce seuil. Une des parties du livre s'attache à décrire les expériences concrètes ayant amené à cette conclusion. Wolfram a appelé cette loi le "principe d'équivalence computationnelle". Atteindre ce seuil de complexité signifie notamment posséder des propriétés d'indécidabilité et d'irréductibilité si difficiles à traiter pour le formalisme mathématique. On peut commencer déjà à entrevoir la signification finalement très simple de l'observation de Gödel quand il a énoncé son théorème d'incomplétude. Les automates les plus adaptés pour simuler les mathématiques sont les systèmes multichemins. Ces systèmes traitent les théorèmes comme les nœuds d'un réseau, et leurs démonstrations comme les déplacements à l'intérieur de ces réseaux, pour passer d'un théorème à l'autre. Wolfram a fait l'effort d'étudier les systèmes axiomatiques des différents domaines mathématiques (logique, théorie des groupes, algèbre, théorie des ensembles, topologie, analyse réelle, géométrie plane, arithmétique...), mais en étudiant tous les chemins possibles de liaison des théorèmes entre eux. Par cette approche systématique, caractéristique de sa démarche globale dans son livre, il a montré que les mathématiques subissaient les mêmes lois d'irréductibilité et d'indécidabilité que tous les autres automates cellulaires ayant atteint le seuil de complexité suffisant (appelé aussi seuil d'universalité). Il a montré que les mathématiques sous leur forme actuelle n'étaient qu'une forme restreinte parmi toutes les mathématiques possibles. Et il a montré que les choix faits pour étudier telle ou telle partie de ce domaine étendu, été liés à l'historique des mathématiques plutôt qu'à autre chose. Et surtout pas à leur efficacité pour traiter des phénomènes complexes, car ces choix évitaient soigneusement toutes les combinaisons et chemins indécidables, visant par là surtout à se préserver elle-mêmes comme cohérentes, ce qui est normal en quelque sorte pour tout système. Mais cela est en complète contradiction avec les espoirs dont on a pu investir les mathématiques comme outil pouvant décrire le réel le plus largement possible.
Pourquoi le théorème d'incomplétude de Gödel a-t-il paru si obscur, inutile et gênant pour les mathématiciens dans le passé ? Car il pointait cette propriété d'indécidabilité au cœur des mathématiques, et commençait clairement à remettre en jeu leur potentiel. Quels pouvaient être ces objets obscurs nécessaires pour compléter l'arithmétique et ne faisant pas partie d'elle? Le nouveau formalisme que Wolfram et d'autres appellent de leur vœu, et que l'auteur de l'ANKS nomme 'une nouvelle forme de science' se révèle autrement plus puissant sans s'embarrasser de ces objets obscurs, même s'il n'est qu'au début de son existence. Les automates cellulaires semblent être un moyen efficace de le toucher du doigt.
Les mathématiques discrètes existent depuis un certain temps, et les automates cellulaires aussi, mais ceux-ci n'ont pas été étudiés pour eux-mêmes, mais plutôt dans le cadre de telle application mathématique compliquée. Alors qu'une des observations de Wolfram ouvrant la voie pour dépasser les limites des mathématiques, est qu'un système simple comme un automate cellulaire peut générer un comportement hautement complexe, atteignant rapidement le seuil d'universalité et pouvant simuler n'importe quel autre système complexe, naturel ou non. Et cette simplicité, vue par exemple dans les règles décrites au début de l'article, associée à la puissance des ordinateurs actuels, permet de manipuler ces systèmes complexes efficacement de manière systématique, sans s'investir dans la recherche de raccourcis mathématiques pouvant prendre un temps infini pour être découverts, s'ils existent, puisqu'on a affaire à des systèmes indécidables.
Reconnaître ses limites, c'est aussi progresser et se doter des moyens de les contourner.

Einstein disait que seules les lois physiques faciles à exprimer avec le formalisme mathématique pouvaient être repérées. Une solution semble apparaître de manière imprévue pour élargir notre potentiel de découverte de nouvelles lois : changer de formalisme. Pour citer Wolfram là-dessus et sur les relations entre science et mathématiques :
Il n'est pas surprenant qu'il puisse y avoir des résultats dans les sciences où les mathématiques se révèlent pertinentes, car depuis à peu près un siècle l'objectif global des mathématiques fut conçu à un certain niveau comme étant de fournir des idéalisations abstraites sur des aspects de la réalité physique (avec quand même pour conséquence que des concepts comme les dimensions au delà de 3 et les nombres transfinis ne soient pas volontiers admis comme porteurs de sens, même en mathématiques). Mais il n'y a absolument aucune raison de penser que les concepts spécifiques apparus jusqu'ici dans l'histoire des mathématiques puissent couvrir toute la science, et en effet dans ce livre je mets en évidence que la science déborde largement hors de cette couverture. Il fut un temps où le rôle des mathématiques en science servait en philosophie comme indicateur du pouvoir ultime de la pensée humaine. Au milieu du vingtième siècle, particulièrement parmi les physiciens, il y eut de temps en temps quelques étonnements exprimés devant l'efficacité des mathématiques en sciences exactes. Une explication avancée par Albert Einstein disait que seules les lois physiques faciles à exprimer dans notre système mathématique étaient repérables. Tiré des notes de l'ANKS.

Formulé autrement, un des atouts du nouveau formalisme de Wolfram vient du fait qu'il ne raisonne pas par contraintes, mais préconise de dérouler les règles, ce qui est beaucoup plus facile. Car poser un problème en termes de contraintes ne donne aucune indication sur la façon de résoudre ces contraintes (on peut voir la difficulté qu'il peut y avoir à résoudre un simple problème de tangram). Et Wolfram donne quelques exemples de faillites de raisonnements par itération n'arrivant même pas à approcher la solution d'un problème dont on connaît déjà la solution, même par des computations extrêmement longues. D'où la puissance de l'approche systématique permise aujourd'hui par les ordinateurs et les concepts disant que de simples règles peuvent générer des systèmes hautement complexes. Alors que les mathématiques raisonnent plutôt par contraintes.
D'autre part, l'approche continue des phénomènes est typique des mathématiques et tend à compliquer les descriptions inutilement. Wolfram cite d'ailleurs les cinq équations différentielles de base utilisées dont sont issues toutes les autres et souligne leur manque de souplesse et de choix. Alors que l'approche discrète des automates cellulaires est beaucoup moins contraignante. Des théories physiques alternatives basées sur la description d'un univers discret plutôt que continu, où l'espace serait un réseau plutôt que du vide continu, tendraient à lever des paradoxes comme celui de la non-séparabilité, tout comme le paradoxe de Gödel a pu être levé par l'étude de mathématiques alternatives. Mais ceci est le sujet d'un prochain article, basé sur la règle 110 des automates cellulaires.

En conclusion, quand on y réfléchit un peu, il n'est pas étonnant qu'aujourd'hui en plein développement de l'informatique, ce soit un langage de programmation qui postule à remplacer les mathématiques car c'est de cela dont il s'agit. Surtout si c'est un langage symbolique puissant basé sur le concept que tout peut être exprimé symboliquement, permettant à Mathematica, le logiciel que Wolfram a utilisé pour faire les expériences de ce livre, de représenter pratiquement n'importe quel objet abstrait, dont les mathématiques. La lutte entre les standards de remplacement des mathématiques a peut-être commencé et Mathematica semble avoir une longueur d'avance, puisque c'est avec lui que toutes les découvertes présentées dans l'ANKS, débordant largement le champ des mathématiques, ont pu être formalisées précisément. Même si la vague de découvertes sur l'émergence et la complexité existe sous d'autres formes et impliquent d'autres équipes de chercheurs issues d'autres milieux que les mathématiques et la physique, Wolfram prend date avec son livre. Finalement cette mise en échecs des espoirs des mathématiques par l'ANKS n'est qu'apparente, elle semble en filigrane transformer leur avantage en ayant produit grâce à leur rigueur le seul formalisme opérationnel pour l'instant capable de certifier ces nouvelles découvertes.

Détail sur le théorème d'incomplétude de Gödel

Pour citer Wolfram pages 782 et 785 : Au début des années 1900, il était largement admis que toutes les propositions qu'on s'attendait à voir vraies ou fausses allaient finalement être démontrées un jour ou l'autre comme vraies ou comme fausses, dans tout système axiomatique raisonnable. Car en ce temps-là, il semblait ne pas exister de limites à la puissance des mathématiques, et aucune fin à la liste des théorèmes pouvant être démontrés. Mais tout change en 1931 quand le théorème de Gödel montre que, au moins dans un système d'axiomes non infini et contenant de l'arithmétique standard, il doit inévitablement y avoir des déclarations ne pouvant pas être démontrées comme vraies ou fausses en utilisant les règles du système axiomatique lui-même. Ce fut un grand choc pour la réflexion de l'époque au sujet des fondements des mathématiques. Et d'ailleurs depuis ce jour, le théorème de Gödel a continué d'être largement regardé comme un résultat surprenant et assez mystérieux. Mais les découvertes de l'ANKS commencent enfin à le rendre apparemment inévitable et concrètement presque évident. Car d'un certain point de vue, il peut être considéré comme encore une autre conséquence du très général principe d'équivalence computationnelle.
La démonstration originelle du théorème de Gödel était basée sur la considération de la déclaration particulière auto-référentielle "Cette déclaration est impossible à prouver". Au début, il ne semble pas évident qu'une telle déclaration puisse jamais être formulée comme une déclaration arithmétique. Mais si elle arrive à l'être, alors on peut voir qu'il s'en suit aussitôt --comme cette déclaration le dit--qu'elle ne peut pas être prouvée, car autrement il y aurait incohérence. [Si tout est démontrable--avec cohérence et complétude-- alors cette déclaration aussi. Malheureusement elle déclare qu'elle n'est pas elle-même démontrable. Donc la démontrer vraie ne semble pas possible. Et si elle est fausse, cela revient au même car il deviendrait donc possible de prouver, qu'il est impossible de la prouver - NdT].
En fait, la principale difficulté du théorème de Gödel concerne la façon dont cette déclaration peut effectivement être significativement codée comme une déclaration arithmétique--en faisant un effort équivalent à l'établissement de l'universalité de l'arithmétique.

Avec le codage mathématique originel, la déclaration serait astronomiquement longue à écrire. Mais avec le codage sous forme d'automates cellulaires, on voit d'une part qu'il est banal de rencontrer de telles situations d'indécidabilité. Et le théorème de Gödel n'est plus qu'une confirmation de ce qui est observé pratiquement partout ailleurs dans les autres systèmes ayant atteint le seuil d'universalité, et qui sont légions.
D'autre part, en réalisant que les mathématiques s'emploient surtout à défendre leur cohérence interne, en choisissant les chemins d'un théorème à l'autre qui évitent l'indécidabilité pourtant réelle, on remet en question la démarche de la preuve et de la démonstration au sens mathématique. Car cela équivaut à chercher des raccourcis qui n'existent pas forcément, ou qui sont extrêmement difficiles à trouver, vu que l'irréductibilité est un phénomène courant, même si les mathématiques l'évitent soigneusement.

N.B. pour se réconcilier avec les mathématiques à l'usage de tous ceux comme moi qui ont subi leur diktat pendant leur scolarité, et qui ont été plus ou moins centrifugés hors des filières scientifiques à cause de leur formalisme constamment présenté comme omnipotent, alors que je sentais bien que c'était louche.

Comment aller directement au sujet en se déplaçant à l'intérieur du livre de Wolfram ?
D'abord lire la préface et les chapitres 1 et 2. Puis les deux premières et les deux dernières sections du chapitre 3 traitant des automates cellulaires en général. Ensuite le chapitre 4 sur les nombres.
Passer au chapitre 6 en lisant les deux premières sections sur les 4 classes de comportement et la dernière section sur les structures de ces automates de classe 4. La section du chapitre 7 sur les problèmes de contrainte à satisfaire serait bienvenue. Puis les quatre premières section du chapitre 10 sur la perception, traitant de la définition de la complexité, et la section vers la fin parlant des mathématiques traditionnelles. Puis dans le chapitre 11, les sections sur le phénomène d'universalité au début, et sur le seuil d'universalité, vers la fin. Pour finir, attaquer franco le chapitre 12 jusqu'aux implications pour les mathématiques et leurs fondements.

A savoir : Stephen Wolfram fera une intervention en vidéoconférence sur son livre, le 6 Octobre prochain à 17h00 au Palais des congrès de la Porte Maillot à Paris, dans le cadre de la conférence sur la sortie de la nouvelle version 5 de son logiciel Mathematica. Renseignements sur www.wolfram.com/services/seminars/paris2004/. Peut-être que les portes vont s'entrouvrir un peu à 17h00 pour les fans encore exclusifs de l'ANKS, qui n'ont pas encore passé le cap du contact direct avec le logiciel qui a permis de le réaliser ? Ou est-ce l'occasion de le faire ?

Pour en savoir plus :
Notre dossier "A New Kind of Science"

© Automates Intelligents 2004