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 r0, r1,..., rn,... 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 P0, P1,...,Pn,... Ž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,a0,a1,...,an,... o chaque an vaut 1 si le programme Pn 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 Pn 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 Pn, 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/2n 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/2n.

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/2n. PrŽcisŽment: ½U = · 1/2n, 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/2i de tous ceux qui se sont arrtŽs. La suite croissante xn 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 xn qui converge vers la constante. Certaines mŽthodes sont rapides (par exemple on gagne un chiffre exact en passant de x n ˆ xn+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/10n (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 2n 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 xn=pn/qn, cette suite vŽrifiant de plus que pour tout entier n, |xn - x| < 1/2n.

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 xn soit infŽrieure ˆ 1/2 n).

On montre que cette dŽfinition est Žquivalente ˆ:

¥ x s'Žcrit en binaire sous la forme x=0,a0a1a2... avec une fonction n --> an (chaque ai 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 xn=pn/qn (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.