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

Classé dans : Apprendre, Connaissance | 0

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.)

kolmogorov
Andreï Kolmogorov est né le 25 avril 1903 à Tambov (à 500 km au sud-est de Moscou). Kolmogorov est une sorte d’Euclide du XXiè siècle, son travail de formalisation des probabilités est comparable à celui qu’avait réalisé son illustre ainé à propos de la géométrie. C’est aussi un mathématicien « au pays des Soviets », dont la production scientifique commence avec la Révolution d’Octobre 1917, et dont la vie se termine au début de la Perestroïka.
La complexité de Kolmogorov (nommée d'après le mathématicien Andreï Kolmogorov), nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction permettant de quantifier la taille du plus petit algorithme nécessaire pour engendrer un nombre ou une suite quelconque de caractères. Cette quantité peut être vue comme une évaluation d'une forme de complexité de cette suite de caractères.
Complexité de Kolmogorov et entropie de Shannon 
un exemple tout simple.
 La suite de dix chiffres suivante
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 
nous semble beaucoup moins complexe que la suite 
1, 2, 3, 1, 0, 9, 0, 8, 0, 5.
 Pour coder brièvement la première, il suffit d’écrire « dix fois un », alors que la seconde nécessite plus de « détails ».
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.

DoronZeilberger
Doron Zeilberger est un mathématicien et informaticien israélo-américain né le 2 juillet 1950 à Haïfa, Israël. Son domaine de recherche est la combinatoire et les algorithmes de sommation rapide.

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).

JonathanBorwein
Jonathan Michael Borwein is currently Laureate Professor in the School of Mathematical and Physical Sciences at the University of Newcastle (NSW)
DavidH.Bailey
Senior Scientist (retired), Computational Research Department, Lawrence Berkeley National Laboratory.wein, 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.

turing-machine
Une machine de Turing

 

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.

->Une proposition (on dit aussi énoncé) est dite décidable dans une théorie axiomatique, si on peut la démontrer ou démontrer sa négation dans le cadre de cette théorie.
->Un énoncé mathématique est donc indécidable dans une théorie s’il est impossible de le déduire, ou de déduire sa négation, à partir des axiomes de cette théorie.

En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. Pour distinguer la notion d’indécidabilité de la notion d’indécidabilité algorithmique , on dit aussi que l’énoncé est indépendant du système d’axiomes.
Citons quelques problèmes indécidables comme Le célèbre postulat des parallèles d’Euclide, relativement à sa géométrie, ou encore de l’hypothèse du continu relativement à la théorie des ensembles usuelle, selon laquelle il n’y a pas de cardinal entre celui de l’ensemble des entiers naturels et celui de l’ensemble des nombres réels, dont Paul Cohen a démontré, en 1963, qu’elle était indécidable.
Une théorie mathématique pour laquelle tout énoncé est décidable est dite complète, sinon elle est dite incomplète.

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.

Laissez un commentaire