Connaissez-vous le nombre aléatoire Oméga de Chaïtin?

Classé dans : Connaissance | 1

Gregory Chaitin est un mathématicien et informaticien et a son point de vue sur la notion formelle de hasard:

  • Le hasard selon la définition de Chaitin correspond à un défaut de structure (pattern), et à une incompressibilité de l’information nécessaire pour le générer
    (L’incomplétude est difficile à imaginer pour une suite finie de nombres, en effet, il est toujours possible de créer un algorithme générant cette suite finie. Par contre, concevoir un algorithme plus petit (codé avec moins de bits) que la suite elle-même n’est possible que pour un ensemble très restreint de suites de nombres. La complexité de Kolmogorov (nommée d’après le mathématicien Andreï Kolmogorov), est une mesure de cette compressibilité de l’information.Le succès de la physique tient à sa capacité à simplifier des phénomènes complexes jusqu’à les faire tenir en une petite équation. Par exemple, il est possible de modéliser l’attraction gravitationnelle entre deux corps en combinant les attractions individuelles de chacun des atomes constituants les corps et en ne considérant que le centre de masse résultant. Malheureusement, ce principe de compression de l’information ne s’applique pas pour tous les phénomènes, certains algorithmes sont incompressibles.)
Une suite de nombres est dite aléatoire si, pour l’engendrer, il n’existe pas d’autres moyens que de l’écrire complètement
A contrario, si on peut compacter ce nombre par une technique quelconque, alors il n’est pas aléatoire
  • Martin-Löf donne une définition statistique du hasard
  • Il a été démontré que les deux définitions sont équivalentes
    • la définition de Chaitin       – basée sur la complexité
    • et celle de Martin-Löf         – basée sur les statistiques
Gregory Chaitin est un mathématicien et informaticien argentino-américain. C'est un spécialiste de l'algorithmique.
Gregory Chaitin est un mathématicien et informaticien argentino-américain. C’est un spécialiste de l’algorithmique.
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 vérifier 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.
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.

Les propositions indécidables de Gödel ont eu de nombreux prolongements en informatique.Plus de 85 ans après sa découverte en 1930, le théorème d’incomplétude de Kurt Gödel (toute théorie formelle non contradictoire des mathématiques contient des propositions indécidables, c’est-à-dire dont on ne p o u r ra démontrer ni qu’elles sont justes ni qu’elles sont fausses) suscite encore des interrogations et fait l’objet de compléments.Très tôt, avant même la conception des premiers ordinateurs, A. Turing élabora la théorie des machines de Turing, qui introduisaient des concepts encore en vigueur actuellement : entrée, sortie, mémoire et programme.

Une machine de Turing est un appareil théorique disposant d’une bande infiniment longue sur laquelle une tête peut lire et écrire, d’un registre de mémoire (fini) et d’un « processeur » capable de réaliser les opérations suivantes :

  • déplacer la bande vers la droite / la gauche ;
  • modifier l’état du registre selon sa valeur actuelle et la valeur sur la bande ;
  • écrire ou effacer une valeurs sur la bande.

Le traitement continue jusqu’à ce que la machine atteigne un état particulier qui provoque son arrêt — ceci ne se produit pas forcément.
Le problème de l’arrêt consiste à déterminer, étant donné une machine de Turing et un jeu de programme / données initiales, si la machine va s’arrêter. Turing a prouvé que cette question était formellement indécidable.

Les nombres Ω de Chaitin.

« Pour définir un nombre (réel), il est nécessaire et suffisant de donner toutes ses décimales »…
Cette conception est trop naïve !
Tout d’abord, il est impossible de calculer tous les nombres réels. En effet, calculer un nombre consiste à faire fonctionner un programme qui calcule ses décimales, mais l’infinité (dénombrable) des programmes est strictement inférieure à celle, indénombrable, des réels. Ne peut-on alors faire comme si les nombres non calculables n’existaient pas ? Non, car il est possible de les définir avec précision. Un exemple : énumérons tous les programmes possibles en une suite (Pn) nN puis définissons le réel T par ses décimales :

  • la nième décimale de vaut 0 si Pn s’arrête ;
  • sinon la nième décimale de vaut 1.

On ne peut pas calculer T en vertu du théorème de l’arrêt. On peut connaître une infinité de ses décimales (celles qui correspondent aux programmes dont on sait s’ils s’arrêtent ou non), mais une infinité d’autres resteront cachées.
Les nombres Ω, inventés par G. Chaitin, sont « encore moins calculables » : dans leur cas, il est seulement possible de connaître un nombre fini des décimales. Pourtant un tel nombre est défini précisément : c’est la probabilité pour qu’une machine de Turing [1] universelle à programmes autodélimités s’arrête.
Une machine de Turing est dite universelle si elle est capable de réaliser n’importe quel programme — chaque ordinateur courant en est une bonne approximation.
Un programme est autodélimité s’il contient en lui-même l’indication de sa propre fin, p. ex. sous la forme d’une instruction END. C’est pratiquement toujours le cas. Mais cette précaution théorique est nécessaire pour donner un sens à la probabilité d’arrêt du programme.
La réalisation pratique de la définition soulève quelques difficultés, toutefois surmontables relativement aisément.
On connaît quelques propriétés des nombres Ω : ils sont irrationnels et même transcendants. Leurs décimales sont équiréparties en toute base. Ce sont de nombres-univers en toute base (toute succession de chiffres y est présente). Ils sont aléatoires au sens le plus exigeant de cette notion. Ils constituent un ensemble est stable par l’addition et, sous restriction, par la multiplication. Bien qu’ils soient approchables (étant limites de suites de rationnels : Ω = lim(rn) ), ils ne sont pas calculables (ce qui demanderait en plus une majoration de l’erreur du type |Ω – rn| ≤ 1/2n). Cette distinction signifie que s’il est possible d’approcher arbitrairement un nombre Ω , on ne peut juger de la qualité de l’approximation effectuée.
Cependant, dans un cas particulièrement simple, un calcul de quelques décimales d’un nombre Ω a été effectué.
Les nombres de Chaitin ne sont pourtant pas la limite de l’incalculabilité : R. Solovay [2] a construit récemment (2000) un nombre Ω particulier dont aucune décimale ne peut être calculée. Il modifie les premiers chiffres d’un nombre Ω (ceux qu’on pouvait espérer calculer) de telle sorte qu’ils échappent à la théorie classique des ensembles.
Les nombres Ω connaissent le secret de toutes les conjectures mathématiques (car chacune se ramène au non-arrêt d’un programme cherchant un contre-exemple, dont on pourrait juger en examinant les décimales convenables d’un nombre Ω bien choisi…), mais ils ne nous en diront jamais rien.


Cette présentation des nombres Ω est tirée d’un article paru sous la plume de J.-P. Delahaye dans la revue Pour la Science n° 295 (mai 2002), pp. 98-103, lisible ici.


Note

note 1 cf. le problème de l’arrêt.
note 2 l’auteur de l’axiome de Solovay : « toute partie de R est Lebesgue-mesurable », incompatible avec l’axiome du choix dans sa version la plus forte bien que relativement consistant avec la théorie ZF de base.

propomega
Jean-Paul DELAHAYE qui  est professeur à l’Université
de Lille et chercheur au Laboratoire d’informatique
fondamentale de Lille (LIFL) publie un article où il montre
où il présente ce nombre Oméga de Chaitin et développe quelques unes de ses propriétés:
Ces résultats « aggravant » en quelque sorte les théorèmes de Gödel où la notion d’indécidabilité entre pour la première fois dans les Mathématiques et J-P Delahaye propose même une synthèse d’articles récents sur le nombre Oméga qui montre que presque tout est indécidable.

Répondre à international removalists Annuler la réponse

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *