Les nombres Ω de Chaitin

Sémantique

Logique

Infini

Mesure

Probas

Nombres

Physique

"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 (P_n) _n∈ℕ puis définissons le réel T par ses décimales :

• la n^ième décimale de T  vaut 0 si P_n s'arrête ;
• sinon la n^ième décimale de T  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 W, 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 [¹] 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(r_n) ), ils ne sont pas calculables (ce qui demanderait en plus une majoration de l'erreur du type |Ω − r_n| ≤ 1/2ⁿ). 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 [²] 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

[¹] cf. le problème de l'arrêt.

[²] l'auteur de l'axiome de Solovay "toute partie de ℝ 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.