Les nombres oméga

Jean-Paul Delahaye

Les nombres oméga sont déroutants: ils sont parfaitement définis, et pourtant incalculables. Toutefois, plus on examine les nombres oméga, plus leurs propiétés apparaissent extraordinaires

Il y a un peu plus de vingt ans — en1979 — Martin Gardner aidé de Charles Bennett publiait un article sur un nouveau nombre aux propriétés tellement étranges qu'il fut perçu comme un paradoxe. Ce nombre découvert par Grégory Chaitin fut appelé oméga et noté Ω. Le symbole Ω a été fréquemment utilisé en mathématiques pour désigner divers objets, mais il semble qu'on est en train prendre l'habitudede réserver ce symbole pour le nombre de Chaitin, comme au début du XVIIIe siècle l'usage s'est définitivement établie de n'utiliser la lettre π que pour la constante d'Archimède.

Le nombre Ω appartient à une famille infinie de nombres, les nombres oméga de Chaitin. Ces nombres oméga sont déconcertants car chacun concentre une conjonction invraisemblable d'étrangetés. Une sous-classe des nombres oméga de Chaitin, les nombres oméga de Solovay aggravent encore le tableau. Ces classes de nombres bizarres sont que les classes des nombres rationnels, algébriques ou transcendant. Nous allons examiner ces êtres abstraits extremês, à la frontière de l'absurde, qui nous forcent à nous interroger sur la nature de la connaissance mathématique.

Nombres calculables

Procédons pas à pas en cheminant dans l'univers des nombres réels, pour examiner la définition des nombres oméga et en goûter toutes les singularités.

Les nombres réels sont les nombres, commee e = 2,7182818284590..., qui écrits en base 10 par example, peuvent se poursuivre indéfiniment (c'est le cas pour e). Ceux qui ne se poursuivent pas indéfiniment (comme le fameux 6,55957) sont les décimaux. Parmi ceux qui se poursuivent indéfiniment certains le font d'une manière périodique comme 24/110 = 0,21818181818... et les nombres qui sont périodiques à partir d'un certain endroit de leur développement sont des quotients de deux entiers (dénommé nombres rationnels). Les nombres irrationnels (exemple √2) ne sont pas les quotients de nombres entiers et leurs décimales ne sont pas périodiques.

À cause de l'infinité de leurs décimales les nombres ne sont pas réels introduisent subrepticement des difficultés logiques dont la gravité est plus grande que nous l’imaginons et ce sont ces difficultés que les nombres oméga exacerbent. Examinons-les.

D'abord l'infinité des décimales entraîne que les nombres réels ne sont pas dénombrables: il n’existe aucune numérotation r₀, r₁,..., r_n,... qui fasse la liste exhaustive des réels (c'est à Cantor que nous devons ce résultat). Ainsi, l'ensemble des nombres réels constitue un ensemble infini plus gros que l'ensemble infini des nombres entiers et des nombres rationnels (puisque, merci Cantor, cet ensemble de rationels a la même taille que l'ensemble des entiers).

Une conséquence parfois oubliée de cette non-dénombrabilité est que nous ne pourrons jamais calculer tous les nombres réels: les nombres calculables sont, par définition, ceux pour lesquels il existe un programme d'ordinateur qui lorsque nous le laissons fonctionner indéfiniment, en égraine les décimales les unes après les autres. Or il n'y a qu'une infinité dénombrable de programmes: nous pouvons, par exemple, les numéroter tous en considérant les ensembles de programmes qui ont 1, 2, 3,…,n, n + 1,… symboles. Chaque ensemble contient un nombre fini de programmes, donc est numérotable, et tous les programmes sont ainsi dénombrés; c’est ce classement des programmes que nous utiliserons par la suite. Il s’ensuit qu’il n’y a donc pas assez de programmes pour calculer tous les réels. Bien sûr, tout rationnel est calculable, ainsi que toutes les constantes habituelles des mathématiques classiques: π, e, log(2), e+π, sin(1), etc. Dans chaque cas, leur définition (par exemple par une série e = 1 + 1/1! +1/2! + 1/3! + ...) donne des programmes calculant une à une leurs décimales.

Les nombre réels non calculables doivent-ils être pris au sérieux et ne pourrions-nous pas ignorer leur existence? Non, car la théorie du calcul, dévelopée dans les années 1930 par Kurt Gödel, Alan Turing et quelques autres logiciens, en plus d’en démontrer abstraitement l’existence (à partir de considérations sur la non-dénombrabilité), définit avec une parfaite précision des nombres non calculables, qui, de ce fait, ont un statut d’object mathématique comparable à π et e.

Une procédé simple pour définir un nombre non calculable va nous rapprocher des nombres Ω. Il est fondé sur le problème de l’arrêt des programmes. La question de l’arrêt des programmes est d’importance théoretique et pratique: nous avons tous écrit des programmes qui tournaient à dessein sans jamais s’arrêter comme le programme c := 1; tant que c > 0 faire c := c + 1; fin. Il n’y a qu’une alternative: un programme lancé peut, soit s’arrêter au bout d’un temps fini, soit au contraire, se poursuivre indéfiniment.

Etablissons la liste de tous les programmes possibles P₀, P₁,...,P_n,... écrits par exemple en Java (un langage de programmation très utilisé aujourd'hui) en les classant par famillie de taille comme décrit précédement. Considérons alors le nombre réel dont le développement décimal est: t = 0,a₀,a₁,...,a_n,... où chaque a_n vaut 1 si le programme P_{n s'arrête, et 0 sinon s’il continue indéfinement.}

L'indécidabilité de l'arrêt d'un programme ("il est impossible d'écrire un programme A qui examinant un programme quelconque P_n indique, en un temps fini si P_{s'arrête ou s'il tourne
indéfiniment") démontrée en 1936 par Alan Turing a pour conséquence que le
nombre réel t n'est pas
calculable: le programme A n’existe pas.
Notons que, si le programme A
existait, il appartiendrait à la liste de P_n, et nous voyons qu’il
devrait opérer sur lui-même pour déterminer s’il s'arrête: l’application de A
à lui-même est le coeur de la démonstration
de Turing.}

Ainsi certains nombres comme t ne sont pas calculables mail ils sont connus, car définis sans la moindre ambiguïté, et pourtant sont inconnaissables, car aucun programme ne peut en égrainer les chiffres. Le monde mathématique est ainsi fait: certains de ses objets peuvent être vus (définis) mais pas touchés (calculés).

Les oméga sont bien pires

Les nombres oméga sont comme ce nombre t, mais en pire. Remarquons qu'il existe de nombreux programmes (une infinité dénombrable) dont nous savons s'ils s'arrêtent, par example les programmes PRINT 0, PRINT 1, PRINT 3, etc. ou s’ils ne s'arrêtent pas. Donc nous pouvons connaître une infinité de chiffres du nombre t qui n'est donc pas calculable en totalité! En revanche, pour les nombres oméga de Chaitin nous ne pouvons connaître qu'un nombre fini de chiffres d'un nombre oméga de Chaitin.

Qu’entendons-nous par connaître? En mathématiques depuis que la logique a permis au début du XXe siècle la formalisation de théories puissantes, les mathématiciens on pris l'habitude d'indiquer (au moins implicitement) dans quelle théorie on raisonne et avec quel langage on écrit les preuves qu'on propose. La théorie des ensembles ZFC (Zermelo-Fraenkel avec l’axiome du choix) est une théorie satisfaisante pour pratiquement toutes les mathématiques et elle sert d'ailleurs de base au grand traité de mathématiques de Nicolas Bourbaki. Les preuves que nous évoquerons ici sont des preuves formulables dans ZFC et il nous suffira de penser que lorsque nous disons "nous pouvons connaître P" cele signifie: il existe une preuve de ZFC qui démontre P. Cette remarque étant formulée, nous n’y reviendrons pas: quand nous affirmerons qu’une tell propriété est démontrable, nous sous-entendrons "avec les axiomes de ZFC".

Les nombres oméga de Chaitin sont des nombres réels parfaitement définis, qui, comme nous le verrons dans la suite, non seulement ne sont pas calculables (aucun programme ne peut en égrainer les chiffres, comme c’était déjà le cas pour t) mais dont nous ne connaîtrons qu'un nombre fini de chiffres. La théorie mathématique est incapable de donner des précisions sur les chiffres des nombres oméga que pourtant elle définit parfaitment!

Si Ω est un nombre oméga de Chaitin donné et si n est un entier fixé, alors l'un des deux énoncés suivants est vrai:

le n-ième chiffre binaire de Ω est un 0

le n-ième chiffre binaire de Ω est un 1

Pourtant dès que n est assez grand, aucun de ces deux énoncés n'est démontrable. Enoncé brèvement, si Ω est un nombre de Chaitin alors, les chiffres de Ω, sauf pour un nombre fini d'entre eux, sont indécidables.

Un concentré pur d'indécidabilité

Tout cela avait étonné dans la décennie 1970 ou les mathématiciens avaitent réalisé à quel point des objets parfaitement précis pouvaient être inconnaissables. Cette quintessence d'indécidabilité des nombres oméga de Chaitin vient pourtant d'être dépassée!

En effet, en étudiant les nombres oméga de Chaitin et en exploitant un vieux théorème démontré par Stephen Kleene en 1952 (le théorème de récursion) le mathématicien Robert Solovay a découvert que certains d'entre eux (que nous appellerons nombres oméga de Solovay) tout en étant parfaitement définissables sont totalement inconnaissables. En clair, si Ω est un nombre oméga de Solovay alors aucun chiffre de Ω ne peut en être connu. Notons que Solovay avait déjà acquis une certaine célébrité en 1970 pour un résultat important de logique. Trente ans plus tard, il est le héros d'un nouvel exploit contredisant ainsi un préjugé tenace qui veut que la productivité d'un mathématicien s'épuise très rapidement avec l'âge.

Ces sommets d'indécidabilité que sont les oméga de Solovay montrent à quel point l'introduction en apparence anodine de nombres ayant une infinité de décimales peut, lorsqu'on en tire toutes les conséquences, conduire à des situations au bord de l'absurde et, en tout cas, propres à plonger dans un abîme de perplexité tout être doué de bon sens: comment, ce qui est parfaitement précis, peut-il être parfaitement et définitivement inconnaissable!

Mais quelle est la définition practique des nombres oméga?

Les nombres oméga de Chaitin sont «les probabilités d'arrêt des machines universelles à programmes autodélimités». Ourk! Quelques explications vont éclairer cette définition.

Une machine universelle U est une machine qui, moyennant de bons programmes, est capable de calculer toute fonction calculable par un programme. Tous les ordinateurs contemporains sont de telles machines universelles dont le concept a été introduit par Turing en 1936. L'exigence que les programmes soient autodélimités signifie qu'il faut interdire que le début d'un programme correct pour la machine U, soit un autre programme correct pour U. Une façon d'obtenir cette propriété est de prévoir dans le langage de programmation de la machine une séquence indiquant la fin des programmes: nous conviendrons, par exemple, de terminer tout programme de U par la suite des quatre symboles "E" "N" "D" ".", suite qu'on ne pourra utiliser qu'une seule fois dans un même programme. Il existe dans les séquences d’ADN, de telles séquences de bases indiquant la fin d’un gène.

Le fait que les programmes soient autodélimités (quelque chose en eux-mêmes indique leur fin), permet d'attribuer une probabilité à chaque programme P de la machine U. Pour ce faire, tirons à pile ou face les décimales consécutives d’un programme P jusqu’à ce que l’on obtienne la suite correspondant à la transcription en binaire de "E" "N" "D" ".". Le programme P sera une suite de n chiffres telle que 0110101101001. La probabilité d’obtenir une telle suite est 1/2ⁿ car chaque chiffre a une probabilité 1/2 d’être le bon, c’est-à-dire celui de P. Il s’agit bien d’une probabilité car on peut effectivement tirer au hasard des programmes par une procédé qui donne P avec la probabilité 1/2ⁿ.

Imaginons maintenant qu'on utilise le même procédé pour engendrer au hasard des programmes de la machine universelle U, et qu'à chaque fois qu'on trouve un programme correct pour U, on le fasse fonctionner. Alors, ou bien le programme tourne indéfiniment ou bien il finit par s'arrêter. La suite de lancés de la pièce conduit donc parfoisà l'arrêt, parfois à un calcul infini (soit parce qu'on ne tombe jamais sur un programme correct, soit parce que le programme determiné ne s'arrête pas). La probabilité lorsque ce procédé concret est mis en œuvre, d'arriver à l'arrêt de U est le nombre oméga de Chaitin associé à la machine universelle U et on le note Ω_U. Pour chaque machine universelle, le nombre Ω_U est parfaitement défini et aussi bien characterisé ques les nombres π ou e.

A chaque machine universelle à programmes autodélimités U correspond un nombre oméga de Chaitin; or comme il y a une infinité dénombrable de telles machines U, il y a une infinité dénombrable de nombres oméga de Chaitin Ω_U.

Les nombres oméga de Solovay sont définis à partir d'une classe particulière de machines universelles spécialement concoctées pour que la théorie ZFC ne puisse rien en savoir. La méthode pour définir les nombres oméga de Solovay consiste à transformer une machine universelle U de façon à en modifier les premiers chiffres pour qu'ils échappent à ZFC. Cette définition est un tantinet sibylline, mail les détail este techniquement trop compliqué pour être présenté ici, ce qui est compréhensible: elle a échappé pendant plus de 20 ans aux mathématiciens…

Remarquons que le nombre Ω_U de Chaitin est, par définition, une somme de nombres de la forme 1/2ⁿ. Précisément: Ω_U = ∑ 1/2^{n, la somme étant prise sur
tous les n qui sont des longueurs de
programmes de U s'arrêtant.}

La définition peut donner lieu à un procédé pratique d'approximation de Ω_U. On prend un certain nombre de programmes (par exemple tous ceux dont la longueur i est inférieure à n), on les fait fonctionner un certain temps (par exemple pendant n étapes de calcul) et on additionne les 1/2ⁱ de tous ceux qui se sont arrêtés. La suite croissante x_n ainsi définie converge vers Ω_U.

De qui se moque-t-on?

Vous devez être inquiet et vous commencez à vous dire que je me moque de vous. D'une part je prétends que les Ω_U ne sont pas calculables (et même totalement inconnaissables dans le cas des nombres de Solovay) et en même temps je propose un procédé concret pour approcher ces Ω_U, c'est-à-dire les calculer!

Non, je ne me moque pas de vous et toute la subtilité des nombres oméga est concentré là. Si U est une machine universelle à programmes autodélimités on peut réellement construire une suite croissante de nombres rationnels qui converge vers Ω_U mais cette suite convergera tres lentement. Si lentement que vous ne n'aurez jamais la certitude d'avoir plus que quelques chiffres exacts de Ω_U. Dans le cas des nombres de Solovay, vous n'aurez même jamais aucun chiffre avec certitude. La convergence vers Ω_U est d'ailleurs si lente qu'elle est plus lente que la convergence de n'importe quelle suite calculable croissante vers un nombre calculable (on a récemment démontré le beau résultat que cette lenteur extrême est une propriété caractéristique des nombres oméga).

Pour les constantes mathématiques usuelles comme π, on connaît en général plusieurs méthodes de calcul, chacune produisant une suite de nombres x_n qui converge vers la constante. Certaines méthodes sont rapides (par exemple on gagne un chiffre exact en passant de x_n à x_n+1), d'autres peuvent être plus lentes. Le numéricien préfère bien sûr les méthodes rapides et on peut dire que son art face aux constantes mathématiques consiste à inventer des méthodes à convergence rapide. Lorsqu'on a affaire à un oméga de Chaitin on sait de manière définitive et absolue que cet art du numéricien sera impuissant. Non seulement aucune méthode ne sera rapide, mais de plus à chaque fois qu'on disposera d'une méthode d'approximation on ne pourra pas savoir avec quelle vitesse elle fournit les chiffres de la constante oméga calculée.

Les propriétés des nombres oméga

On peut envisager toutes les machines universelles et tous les nombres oméga associés. La classe infinie des nombres oméga de Chaitin est donc dénombrable, comme l'est d'ailleurs celle des oméga de Solovay. De plus, de nombreuses connaissances ont été accumulées les concernant. Il n'y a pas de paradoxe dans le fait qu'on puisse démontrer des propriétés précises des oméga (y compris des oméga de Solovay) alors qu'on ne peut pas calculer leurs chiffres. Dans le monde réel pour avoir accès à une connaissance générale — par exemple que "e poids moyen des américains est supérieur au poids moyen des européens" — il faut assembler des connaissances particulières. Dans le monde mathématique ce n'est pas forcément le cas: on peut connaître quelque chose de général concernant un nombre Ω — par exemple "la fréquence des 1 et celle des 0 est la même dans l'écriture binaire de Ω" — et en même temps ne connaître aucun chiffre particulier de Ω. Encore une étrangeté du monde mathématique!

Voici quelques unes des propriétés démontrées des nombres oméga.

— Tous les nombres oméga sont irrationnels et transcendants (aucune équation polynomiale à coefficient entier n'a pour solution un nombre oméga).

— Tous les nombres oméga ont des décimales équiréparties: la suite de leurs chiffres en base 10 comporte un dixième de "0", un dixième de "1", ..., un dixième de "9" et on a une propriété analogue en toute base de numération.

— Tous les nombres oméga sont des "nombres univers" en toute base: toute séquence finie de chiffres y est présente. On peut même préciser que toute séquence finie de n chiffres décimaux y est présente avec la fréquence 1/10ⁿ (bien sûr on a une propriété analogue dans toutes les bases de numération). En conséquence, dans tout nombre oméga on sait que quelque part il y a une série d'un milliard de 0 consécutifs (rien de tel n'a été démontré pour les constantes comme π ou e).

— Tous les nombres oméga sont aléatoires au sens mathématique le plus fort (le terme consacré est "aléatoire au sens de Martin-Löf" en l'honneur mathématicien suédois qui introduisit ce concept en 1966). Cela implique en particulier que: (a) une méthode programmable pour prédire le n-ième chiffred'un oméga à partir des n-1 premiers ne fait jamais mieux que le hasard; (b) si l’on extrait une sous-suite de la suite des chiffres d'un oméga par un procédé précis algorithmique (par exemple en retenant les chiffres dont les rangs sont des nombres premiers) cette suite sera celle des chiffres d'un nombre irrationnel, transcendant, équiréparti, et aléatoire et sera même celle d'un autre nombre oméga de Chaitin.

— Tous les nombres oméga sont incompressibles. Précisément, pour chaque nombre oméga Ω_U telle que le plus court programme donnant les n premiers chiffres binaires de Ω_U a au moins la longueur n - c (on ne gagne jamais plus de c bits d'information quand on cherche à comprimer le début des chiffres de Ω_U).

— Tous les oméga sont non calculables et pourtant chacun est la limite d'une suite calculable croissante de nombres rationnels (on dit qu'ils sont approchables). La dite convergence est plus lente que la convergence de toute suite calculable de rationnels vers un nombre calculable.

— Un nombre oméga peut commencer par n'importe quelle séquence finie de chiffres. Il y a donc un nombre oméga qui commence par 3,14, un autre qui commence par 3,1415, un autre qui commence par 3,14159 etc.). Notons toutefois que les machines universelles ayant pour nombre oméga ces nombres-là seront construites artificiellement.

— La somme de deux nombres oméga si elle est inférieure à 1 est un nombre oméga, de même que le produit (ces belles propriétés ne sont pas vraies pour les nombres irrationnels, ou pour les nombres transcendants (par exemple, π/4 + (2-π/4) = 2)).

La raison profonde de toutes ces propriétés est le fait que la connaissance des n premiers chiffres du nombre de Chaitin Ω_U associée à la machine universelle U, permet de savoir pour tous les programmes de U de longueur inférieure ou égale à n, s'ils s'arrêtent ou non (alors que pour cela il faudrait 2ⁿ chiffres binaires du nombre t associé à U). En clair, Ω_U contient une forme hyperconcentrée d'informations sur le problème indécidable de l'arrêt des programmes de U. De nombreuses conjectures pourraient être résolues (en théorie) si on connaissait les 1000 premiers chiffres binaires d'un Ω_U pour une machine universelle U naturelle (par exemple celle associée au langage de programmation programme Java de votre ordinateur).

Une conjecture comme "tout nombre pair strictement supérieur à 2 peut être écrit comme somme de deux nombres premiers" (conjecture de Goldbach) est en effet équivalente au non arrêt du programme qui cherche un contre-exemple, programme qui a une longueur de quelques centaines de chiffres binaires. Toutes les conjectures de la forme "ZFC permet de démontrer P" si P est un énoncé assez court seraient, elles aussi, résolues (en théorie) par la connaissance de quelques centaines de chiffres binaires du oméga d'une machine universelle naturelle.

Les nombres oméga sont donc non seulement desconcentrés d'informations sur l'arrêt des programmes, mais ce sont aussi des concentrés d'information mathématique.

Pour se consoler du fait que nous ne connaîtrons jamais ne serait-ce que 1000 chiffres d'un oméga "naturel" nous pouvons nous dire qu'extraire l'information de nombres oméga est un travail fini mais invraisemblablement long (d'où les "en théorie" que j'ai utilisé dans les paragraphes précédents) et qu'en conséquence même si on connaissait 1000 chiffres d'un nombre oméga de Chaitin associé à une machine naturelle on en pourrait pas vraiment l'utiliser. Comme l'écrivait Martin Gardner et Charles Bennett "Oméga est, dans bien des sens différents, un nombre cabalistique. Il peut être connu par un humain (vous pourriez l'apprendre si on vous le confiait), mais pas sur la base de la raison. Pour le connaître en détail il faudrait faire un acte de foi, comme on accepte les mots d'un texte sacré."

Bibliographie

C. H. Bennett, M. Gardner. Le nombre aléatoire oméga, in Le Monde Mathématique de Martin Gardner, Bibliothèque Pour la Science, pp 45-49, 1986.

C. S. Calude. Chaitin Ω Numbers, Solovay Machines,and Incompleteness, in Theoretical Computer Science, 2002.

http://citeseer.nj.nec.com/calude99chaitin.html (à lire pour une exposé précis et complet)

J. P. Delahaye. Information, complexité et hasard, Hermès Science Publication, Paris, 1999 (seconde édition).

J. P. Delahaye. L'intelligence et le calcul, Pour la Science/Belin, Paris, 2002.

R.M. Solovay. A Version of Ω for Which ZFC Can Not Predict a Single Bit, in C.S. Calude, G. Paun (eds.) Finite Versus Infinite. Contribution to an Eternal Dilemma, Springer-Verlag, 2000, pp 323-334.

Quelques Figures

Figure 3. Le définition des nombres oméga

Un nombre oméga de Chaitin est la probabilité qu'une machine universelle à programmes autodélimités s'arrête.

Une machine universelle U est une machine capable de calculer toute fonction calculable par programme. Les programmes (qu’on suppose écrit en binaire) sont dit autodélimités si l’indication de leur fin est donné par eux-memes. Cette fin est, par exemple, 1111 et la séquence 1111 signifie qu’on est arrivé à la fin du programme.

Epreuve conduisant à un succes ou à un échec

• On tire des 0 ou des 1 au hasard en utilisant un procédé équitable, par exemple en lancant une piece de monnaie.

• On poursuit le tirage jusqu'à obtenir un programme pour U. Il se peut que cela ne se produise jamais (car on ne tire jamais symboles indiquant 1111), on considere alors qu’on a un échec.

• Dans le cas ou l’obtient 1111, cele donne un programme pour U, on confie ce programme a U qui le fait fonctionner. Si U avec ce programme s’arrête, on considere qu’on a un succes, si on on considere qu’on a un échec.

Figure 4. Nombres calculables et approchables

A. Par définition un nombre réel x (pris entre 0 et 1) est calculable s'il est la limite d'une suite croissante et calculable par programme de nombres rationnels x_n=p_n/q_n, cette suite vérifiant de plus que pour tout entier n, |x_n - x| < 1/2ⁿ.

Les constantes usuelles sont toutes des nombres réels calculables, car pour chacune d'elles x on connaît une suite de nombres rationnels qui converge vers x, et on sait évaluer l'erreur commise (on sait donc s'arranger pour que l'erreur commise par x_n soit inférieure à 1/2ⁿ).

On montre que cette définition est équivalente à:

• x s'écrit en binaire sous la forme x=0,a₀a₁a₂... avec une fonction n --> a_n (chaque a_i vaut 0 ou 1) qui est calculable par programme (autrement dit il existe un programme qui égraine les chiffres de x);

• il existe un programme qui énumère tous les nombres rationnels inférieurs à x, et un autre qui énumère tous les nombres rationnels supérieurs à x.

B. Un nombre réel est approchable (on dit aussi c.e. pour calculablement énumérable) si, par définition, il est la limite d'une suite croissante et calculable par programme de nombres rationnels x_n=p_n/q_n (c'est la même chose que pour calculable mais sans la deuxième condition portant sur la majoration d'erreur). Une définition équivalente est:

• il existe un programme qui énumère les nombres rationnels inférieurs au nombre réel considéré.

La nuance entre nombres approchables et nombres calculables est subtile, mais, en réalité, elle est énorme et les nombres oméga de Chaitin sont justement des nombres à la fois approchables et non calculables. Les nombres approchables sont tous parfaitement bien définis (on connaît des suites qui convergent vers eux) et pourtant certains d'entre eux comme les nombres oméga ne sont pas calculables. R. Solovay a d'ailleurs démontré que certains nombres oméga sont tels qu'on ne peut connaître aucun de leurs chiffres avec certitude. Parfaitement définis, ils sont inconnaissables.

Figure 5. Le calcul de quelques chiffres d'un oméga

Il existe des procédés qui à partir d'une machine universelle à programmes autodélimités permettent d'en construire d'autres (qu'on qualifiera d'artificielles) qui seront elles-aussi universelles mais dont le nombre oméga commencera par certains chiffres binaires fixés à l'avance, par exemple 01010101010101.

Les nombres oméga associés à des telles machines universelles artificielles sont eux-aussi artificiels et leurs premiers chiffres (choisis arbitrairement) ne portent aucune information.

En revanche, connaître les chiffres d'une machine universelle U à programmes autodélimités précise qui n'a pas été construite de manière adéquate pour avoir des chiffres connus à l'avance est réellement une tâche difficile, car Ω_U contient alors sous forme concentrée l'information sur l'arrêt des programmes de U. Peut-on tenter de calculer quelques chiffres d'un tel Ω_U?

Oui et c'est ce qu'ont fait récemment C. Calude, M.J. Dinneen et C.K. Shu. Ils ont d'abord défini la machine universelle la plus naturelle possible en considérant un jeu d'instructions aussi simple que possible et en adoptant des conventions de notations aussi concises que possible. Ils ont ensuite tenté deconnaître le comportement d'un grand nombre de programmes courts pour U. Ils ont réussi à analyser tous les programmes dont la longueur est inférieur à 84 chiffres binaires (certains conduisent à l'arrêt d'autres non). Ils ont pu en déduire avec certitude les 64 premiers chiffres de Ω_U. Ces chiffres sont:

00000010000001000001100010000110

10001111110010111011101000010000

C'est la première fois qu'on s'attaque au calcul explicite des chiffres d'un nombre aléatoire. Notons qu'il s'agit d'un jeu, car en pratique 64 chiffres binaires sont très insuffisants pour envisager d'aborder des conjectures intéressantes. Peut-être pourra-t-on aller un peu au-delà de 64, mais très vite un blocage grave se produira et il est très improbable que de tels calculs puissent aider à résoudre des problèmes mathématiques ouverts.