Ω, à la limite des mathématiques


Hasard et complexité en mathématiques. Gregory Chaitin.

Flammarion, Nouvelle bibliothèque scientifique, 2009
ISBN : 978-2-0821-0568-2,28 E


Gregory Chaitin a fait toute sa carrière de mathématicien-informaticien au centre de recherches d'IBM à New-York. Son livre est un apercu, pour non-spécialistes, de ses principaux travaux, ce qui explique l'enthousiasme de l'auteur,et ses efforts de pédagogie. Mais le succès est-il au rendez-vous ?

Chaitin s'est appuyé sur la notion de programme informatique pour donner une définition mathématique rigoureuse de ce qu'est un «nombre aléatoire», un nombre (réel, avec une infinité de décimales) choisi au hasard. Il s'est inspiré pour cela d'idées introduites par Emile Borel au début du vingtième siècle.

On définit d'abord la complexité d'un nombre quelconque par l'intermédiaire de la longueur d'un programme informatique minimal le définissant. Un nombre aléatoire est un nombre tel que tout programme permettant de calculer les N premières décimales est de longueur sensiblement égale à N.

Chaitin a ainsi posé les fondements (indépendamment du célèbre mathématicien Andrei Kolmogorov), d'une nouvelle discipline,la théorie algorithmique de l'information.

Après un exposé historique tout à fait abordable de la célèbre «hypothèse du continu» posée au début du vingtième siècle, puis du résultat (1931) de Kurt Gödel sur l'incomplétude (selon lequel Il existe des faits mathématiques vrais mais indémontrables),qui a ruiné les espoirs de l'école axiomatique de David Hilbert, Chaitin explique simplement les travaux d'Alan Turing,inventeur de l'ordinateur –la machine de Turing – sur le problème de l'arrêt, en 1936 . Le problème de l'arrêt est le suivant : existe-t-il un programme universel permettant d'indiquer si un autre programme arbitrairement donné s'arrête au bout d'un nombre fini d'étapes?

La réponse donnée par Turing est négative.

Ensuite, Chaitin nous présente le nombre mystérieux Ω (omega) qu'il a inventé il y a trente ans et qui symbolise en quelque sorte les limites de la connaissance mathématique puisqu'il fait intervenir tous les programmes informatiques (donnés avec leur longueur) qui s'arrêtent. Ce nombre mystérieux est un nombre réel d'une complexité maximale, il est incompressible, c'est à dire qu'aucun programme ne peut en donner les N premières décimales en moins de N lignes de programme. Autrement dit il est incalculable. Mais malgré tout il paraît «presque calculable», et Chaitin explique ses principales propriétés .

Les mathématiciens adoptent dans leur pratique des attitudes philosophiques variées, voire opposées.

Chaitin participe à un courant semi-empiriste,qui considère les mathématiques comme une discipline expérimentale au même titre que la physique,l'expérience se faisant sur ordinateur (Parmi eux : D. Bailey, J. Borwein, D. Zeilberger). L'argument principal de Chaitin à l'appui de cette thèse est le suivant :

Contrairement à l'opinion des mathématiciens «classiques»,le résultat d'incomplétude n'est pas un fait isolé, la plupart des énoncés mathématiques,en particulier les plus intéressants d'entre eux, sont inaccessibles à toute démonstration,il vaut mieux chercher à les verifier expérimentalement ou heuristiquement.

Les revues mathématiques se sont ouvertes à cet état d'esprit. On cherche activement des méthodes informatiques de recherche d'énoncés intéressant,ou de démonstrations,ou de vérification de preuves. Le courant de recherches se développe. On pourra consulter à ce sujet le site de Doron Zeilberger.

Les outils très puissants de l'informatique ont aussi produit dans certains cas un surdimensionnement de l'ego (Exemples: Benoît Mandelbrot et ses fractals, Stephen Wolfram et ses automates cellulaires). Gregory Chaitin, quand il ne se place pas dans la lignée de Leibniz se situe aux côtés des grands maîtres Gödel et Turing (D'ailleurs Kolmogorov est bizarrement oublié de l'index du livre), et veut nous faire prendre son nombre Omega pour le Graal.

Les notes du traducteur ou les compléments introductifs (très approximatifs) auraient dû chercher à corriger cette autoglorification qui tourne au ridicule. Le dernier paragraphe s'intitule «Contre l'excès d'ego».

On ne saurait mieux conclure.