Voir la source de Oméga de Chaitin

[[Fichier:OmegaChaitin.png|thumb|right|upright=1.2|Un nombre Oméga de Chaitin est une suite de [[bit]]s représentant, sous forme concentrée, la solution du [[problème de l'arrêt]] pour tous les programmes d'une [[machine de Turing]] universelle donnée.]]

En [[théorie algorithmique de l'information]], une constante '''Oméga de Chaitin''' (nombres définis et étudiés par [[Gregory Chaitin]]) caractérise de manière univoque et mathématiquement précise un [[nombre réel]], qui possède la particularité d'être [[suite aléatoire|aléatoire]] et de ne pas être [[Nombre réel calculable|calculable au sens de Turing]] : un [[algorithme]] donné ne permet de calculer qu'un nombre fini de ses décimales. Jusqu'à la définition de ce nombre, il n'existait pas d'exemple mathématiquement précis et « concret » de [[suite aléatoire]]<ref>{{en}} Cristian Calude, ''Information and Randomness: An Algorithmic Perspective'', Springer, 1994, p. 181.</ref>.

Techniquement, il est défini comme étant la [[probabilité]] qu’un [[fonction partielle récursive|programme]] auto-délimité<ref>C'est-à-dire que l'indication de la fin de la séquence de bits représentant le programme est contenue dans le programme lui-même, sous forme d'une longueur, d'une séquence de fin, ou toute autre forme de codage. Une autre manière de le dire est que la [[concaténation]] d'une séquence de bits quelconque à la suite d'un programme valide donne nécessairement un programme invalide (n'appartenant pas au langage).</ref>, généré aléatoirement, finisse par s'arrêter. Les programmes en question sont associés à une [[machine de Turing universelle]] ou à un modèle de calcul donné. Il existe donc une infinité de constantes de Chaitin, chacune associée soit à une machine de Turing universelle donnée, soit à un modèle de calcul.

Cette définition permet également de coder, sous la forme la plus compacte possible, la solution du [[problème de l'arrêt]] pour tous les programmes d'un modèle de calcul donné. Comme il est possible de traduire la plupart des problèmes mathématiques en termes de programme informatique qui s'arrête ou non, la connaissance d'un nombre Oméga permet — en principe — de démontrer un grand nombre de [[théorème]]s ou de [[conjecture]]s mathématiques, dont certains encore non résolus à ce jour comme l'[[hypothèse de Riemann]].

Ces nombres apportent un éclairage sur l'[[Complétude (logique)|incomplétude]] des mathématiques, mise au jour par le célèbre [[théorème de Gödel]], ainsi que des éléments d'appréciation en ce qui concerne sa signification et sa portée.

== Définition de la probabilité d'arrêt ==

Soit {{math|''P{{ind|U}}''}} le domaine d'une [[machine de Turing universelle]] {{math|''U''}}, c'est-à-dire l'ensemble des programmes {{math|''p''}} auto-délimités pouvant être exécutés par {{math|''U''}} qui s'arrêtent.

Par définition :
:<math>\Omega_U = \sum_{p \in P_U} 2^{-|p|},</math>
où {{math|{{!}}''p''{{!}}}} est la longueur de {{math|''p''}}.

Ce nombre est un nombre réel, compris entre 0 et 1, représentant la probabilité d'arrêt d'un programme dont les bits sont tirés aléatoirement, un par un, jusqu'à obtenir la séquence de bits définissant la limite du programme.

== Importance du nombre Oméga dans la théorie algorithmique de l'information ==

Pourquoi ce nombre est-il défini ainsi ? Pourquoi est-il si important ?

Un des grands succès de la [[théorie algorithmique de l'information]] est d'avoir permis la définition rigoureuse de la notion de nombre aléatoire, ou de [[suite aléatoire]]. Selon cette théorie, un nombre est aléatoire si et seulement s'il n'existe pas d'algorithme plus petit que la taille même du nombre pour le générer. Pour poursuivre ce succès et exercer la théorie, l'étape naturelle suivante était de se demander s'il était possible d'exhiber et donner ''un exemple de nombre aléatoire'' ainsi défini.

Paradoxalement, bien qu'un nombre réel sélectionné au hasard soit aléatoire avec une probabilité de 1 (c'est-à-dire que quasiment tous les nombres réels sont aléatoires), il est extrêmement difficile d'en exhiber ou d'en décrire un.

En effet, pour exhiber un nombre, il faut soit le nommer, soit le décrire d'une manière cohérente, et montrer que le nombre ainsi désigné « existe », possède un sens, ce qui n'est absolument pas évident ''a priori'' notamment à cause du [[paradoxe de Berry]], et n'est pas ambigu (désigne un et un seul nombre).
Ou alors, il faut donner un algorithme pour le construire et le générer, mais cela est par définition impossible pour un nombre aléatoire.
Enfin, et surtout, il faut prouver que le nombre décrit est bien aléatoire.

Il est encore plus difficile d'exhiber un tel nombre qui possède une signification et des propriétés mathématiques précises, sans être une simple suite de chiffres aléatoires sans signification.

Le nombre Oméga franchit toutes ces difficultés, et est l'exemple le plus emblématique de nombre incompressible, aléatoire, qui peut être désigné sans ambiguïté, et possède un sens et des propriétés profondes et intéressantes. À ce titre, il constitue un élément très important de la théorie algorithmique de l'information.

== Origine, définition et construction du nombre Oméga ==
=== Le nombre de Borel ===

[[Émile Borel]] s'est intéressé à la notion « d'accessibilité » et de définition d'un nombre. Selon Borel, pour qu'un nombre soit « bien spécifié », il faut d'une part que {{Citation|deux mathématiciens, s’ils en parlent entre eux, soient certains qu’ils parlent du même nombre}} et qu'il soit un {{Citation|véritable “être” mathématique}} qui doit {{Citation|pour être intéressant aux yeux des mathématiciens, avoir au moins deux propriétés (en y comprenant celle au moyen de laquelle il a été défini)}}<ref>Émile Borel, ''Les nombres inaccessibles'', Gauthier-Villars, 1951, {{Lire en ligne|lien=http://fr.scribd.com/doc/69439581/Les-Nombres-Inaccessibles-Borel-1952}}, {{p.|20}}.</ref>. Il est effectivement très difficile pour un nombre purement aléatoire de posséder une autre propriété que sa propre méthode de construction.

D'autre part, Borel a imaginé en 1927 un [[nombre réel]], le « nombre qui sait tout » (terminologie de G. Chaitin<ref group="Chaitin 2007">Paragraphe : ''Borel: Know-it-all and unnameable reals''.</ref>), résumant les réponses à toutes les questions formulables dans un langage donné, auxquelles on peut répondre par oui ou par non<ref>''Revue de Métaphysique et de Morale'', 1927, vol. 34, n° {{XXXe}}, p. 271-275, lettre de É. Borel.</ref>. Cette liste de questions constitue une liste infinie, mais [[Ensemble dénombrable|dénombrable]], que l'on peut trier alphabétiquement. On peut alors constituer un nombre, unique et bien spécifié, dont la n-ième décimale binaire est la réponse à la ''n''-ième question.

Ces deux idées contiennent les germes du nombre Oméga. Chaitin, qui connaît très bien l'œuvre de Borel, reconnaît s'être inspiré de ces idées. Mais tout le travail de Chaitin va consister à transformer une idée mathématiquement inexploitable (car les questions et les réponses ne peuvent être mathématiquement formalisées), en un véritable « être mathématique », possédant de nombreuses propriétés démontrables, et deux caractéristiques ''a priori'' contradictoires : être « bien spécifié » et pourtant « inaccessible », non calculable et aléatoire.

=== Le « nombre de Turing » ===

Si l'on recycle l'idée du « nombre qui sait tout » pour définir un nombre dont la ''n''-ième décimale répond au [[problème de l'arrêt]] pour le ''n''-ième programme exécutable par une machine de Turing universelle, nous avons alors une définition précise d'un nombre et qui possède un sens mathématique, car le problème de l'arrêt est formalisé. De plus, étant donné que le problème de l'arrêt est [[Décidabilité|indécidable (au sens algorithmique)]], il s'ensuit que ce nombre est non calculable, ce qui est une condition absolument nécessaire (mais non suffisante) pour qu'il soit aléatoire. Enfin, injecter le problème de l'arrêt dans un nombre est susceptible de lui donner une importance fondamentale, car le problème de l'arrêt est au cœur de problèmes fondamentaux des mathématiques (ceux par exemple liés au [[dixième problème de Hilbert]]).

{{article détaillé|Problème de l'arrêt}}

Tel quel, ce nombre n'est pas encore le nombre Oméga, car il n'est pas aléatoire. En effet, ce nombre (que Chaitin nomme « nombre de Turing » en hommage à l'inventeur du problème de l'arrêt<ref group="Chaitin 2007">Paragraphe : ''What is the halting probability Ω ?''</ref>), est hautement redondant et compressible. Or, une des définitions d'un nombre aléatoire est précisément d'être incompressible<ref>Voir l'article « [[Suite aléatoire]] ».</ref>. Il faut donc trouver un moyen de compresser l'information contenue dans le nombre de Turing, et de la compresser au maximum possible.

=== Le nombre Oméga ===
[[Fichier:ProgramTree.svg|right|upright=0.8|thumb|Représentation d'un ensemble de programmes auto-délimités sous forme d'un [[arbre binaire]].<br>Ici, nous avons quatre programmes possibles, correspondant aux quatre feuilles de l'arbre : "01(00)", "011(00)", "0101(00)", et "101(00)"<br>La procédure de génération aléatoire d'un programme consiste à tirer au sort chaque bifurcation dans cet arbre.]]

Pour comprendre comment sera compressé le nombre Oméga, il est utile de voir pourquoi le nombre de Turing est hautement redondant. En fait, le nombre de Turing utilise N bits pour coder les résultats de N programmes, alors que log<sub>2</sub>(N) bits sont suffisants. En effet, il suffit de connaître ''le nombre'' de programmes de N bits qui s'arrêtent, sans savoir lesquels, pour déterminer les programmes qui s'arrêtent ou non.

Voici comment : si l'on connaît le nombre P de programmes de N bits qui s'arrêtent, alors il suffit de générer tous les programmes de N bits, de faire tourner ces 2<sup>N</sup> programmes et de s'arrêter quand P programmes seront arrêtés (ce qui arrivera certainement dans un temps fini). On est alors sûr que les programmes restants ne s'arrêteront jamais. On connaît donc les programmes qui s'arrêtent et ceux qui ne s'arrêtent pas. P est donc un nombre d'au plus N bits codant les résultats du problème de l'arrêt pour 2<sup>N</sup> programmes.

Le nombre Oméga va utiliser cette idée pour encoder ces informations de manière efficace et incompressible. Le nombre de programmes d'une machine de Turing universelle donnée étant infini, il n'est pas possible de donner un nombre P de programmes qui s'arrêtent (P serait dans la plupart des cas infini), mais on peut donner cette information par la ''proportion'' des programmes qui s'arrêtent parmi tous les programmes, ou — ce qui revient au même — la probabilité d'arrêt d'un programme pris au hasard.

==== De la définition à la formule ====

Le nombre Oméga est donc défini comme étant la probabilité qu'un programme, tiré aléatoirement, d'une machine de Turing universelle, s'arrête.

Le tirage aléatoire consiste à descendre aléatoirement dans l'[[arbre binaire]] représentant tous les programmes possibles pour une machine de Turing universelle U, jusqu'à tirer aléatoirement une ''séquence de fin'', délimitant objectivement la fin de la représentation binaire du programme (voir figure ci-contre). En effet, la définition, et la formule, du nombre Oméga n'est valide que pour les programmes ''auto-délimités'', c'est-à-dire contenant à leur fin une séquence de bits impossible à trouver dans le programme proprement dit. Le nombre de programmes de cette machine de Turing jusqu'à une profondeur N de l'arbre binaire (autrement dit, le nombre de programmes de longueur inférieure ou égale à N) est le nombre de ''feuilles'' de l'arbre.

Pour calculer la probabilité d'arrêt (ou la proportion des programmes qui s'arrêtent), il suffit à première vue de « compter » le nombre de programmes « feuille » qui s'arrêtent, et de diviser par le nombre total de feuilles, mais cela n'est vrai qu'à un niveau N donné. S'il existe un programme court dans l'arbre, on a beaucoup plus de chances de tomber aléatoirement sur lui qu'un programme long : il faut donc « pondérer » l'arrêt d'un programme {{math|''p''}} de taille {{math|{{!}}''p''{{!}}}} par {{math|2{{exp|–{{!}}''p''{{!}}}}}}. Plus un programme est long, plus son poids est faible.

La formule du nombre Oméga en dérive directement ; on additionne les poids pondérés de tous les programmes qui s'arrêtent ({{math|''P{{ind|U}}''}} est l'[[ensemble de définition]] de la machine {{math|''U''}}, c'est-à-dire l'ensemble de tous les programmes qui retournent un résultat et par conséquent s'arrêtent ; {{math|{{!}}''p''{{!}}}} est la longueur en bits du programme {{math|''p''}}) :

{{Bloc emphase|<math>\Omega_U = \sum_{p \in P_U} 2^{-|p|}</math>}}

Cette somme converge et reste inférieure à 1, car les programmes sont auto-délimités : aucun programme n'est le prolongement d'un autre programme (en intégrant la séquence de fin). Par conséquent, un programme court va empêcher l'arbre de se développer après lui : on peut donc lui donner sans danger de divergence le poids de la partie de l'arbre qu'il a empêché de se développer, soit 2<sup>-|p|</sup>. En donnant le bon poids à chaque nœud terminal, on démontre que la somme est majorée par 1, si l'on prend en compte tous les nœuds. Cette propriété est démontrée par les [[Inégalité de Kraft|inégalités de Kraft]].

==== Détermination de l'arrêt des programmes à partir du nombre Oméga ====

Mais le véritable but du nombre Oméga n'est pas de donner la probabilité d'arrêt d'un programme d'une machine de Turing donnée. Son but est de compresser sous la forme la plus compacte possible l'information d'arrêt de tous les programmes de cette machine de Turing. Il est donc nécessaire d'être en mesure de restituer ces informations à partir de la probabilité d'arrêt.

Soit Ω{{ind|''n''}} l'approximation d'un nombre Oméga consistant à prendre les ''n'' premiers bits de ce nombre Oméga. Comment, étant donné ce nombre Ω{{ind|''n''}}, déterminer les programmes de longueur inférieure à ''n'' bits qui s'arrêtent ou non ?

L'inégalité <math>\Omega_n \le \Omega < \Omega_n + 2^{-n}</math> découle logiquement de la convergence de la somme associée à Ω.

Si maintenant on génère tous les programmes possibles de taille inférieure ou égale à ''n'' bits, et si on les fait exécuter simultanément, on pourra calculer une approximation de plus en plus précise de Ω{{ind|''n''}} à chaque arrêt d'une machine, en ajoutant <math>2^{-l}</math>, {{math|''l''}} étant la longueur du programme s'étant arrêté, à l'approximation précédente.

Dès que l'approximation de Ω{{ind|''n''}} atteint une valeur telle que l'ajout du poids d'un programme quelconque non encore terminé rendrait l'approximation supérieure ou égale à <math>\Omega_n + 2^{-n}</math>, nous pouvons être certain que les programmes restants ne se termineront jamais. Les programmes de longueur inférieure ou égale à ''n'' qui ne s'arrêtent pas ont donc été identifiés dans un temps fini, à l'aide des ''n'' premier bits du nombre Oméga : Ω{{ind|''n''}}<ref group="Li Vitanyi">Lemme 3.6.1.</ref>.

On établit au passage la propriété : les ''n'' premiers bits d'un nombre Oméga sont nécessaires et suffisants pour déterminer l'arrêt de tous les programmes de longueur inférieure à ''n'' bits.

==== Preuve que le nombre Oméga est incompressible, et donc aléatoire ====
Soit un nombre ω{{ind|''n''}} représentant le nombre le plus court possible permettant de déterminer le problème de l'arrêt pour tous les programmes jusqu'à une longueur de ''n'' bits.

Soit le programme ''COMPLEXE'' qui, en utilisant ce nombre, détermine la liste des machines qui s’arrêtent de longueur inférieure ou égale à ''n'' bits, collectionne tous les résultats de ces machines, et retourne un nombre ''x'' n'appartenant pas à cette liste. Le programme ''COMPLEXE'' s'arrête.

Par définition, ''x'' ne peut être retourné par un programme de taille inférieure ou égale à ''n''. ''COMPLEXE'' retournant ce nombre, il possède donc une taille supérieure à ''n''. Comme ''COMPLEXE'' intègre ω{{ind|''n''}} dans son programme, il s'ensuit que TAILLE(''COMPLEXE'') = TAILLE(ω{{ind|''n''}}) + constante > ''n''<ref group="Li Vitanyi">Lemme 3.6.2.</ref>.

Le plus petit programme pour calculer les ''n'' premiers bits de Ω a une taille supérieure à  ''n'' – constante, ce qui est la caractéristique d'un [[suite aléatoire|nombre aléatoire au sens de Levin-Chaitin]]. Oméga est donc bien incompressible et aléatoire.

== Enjeux et propriétés du nombre Oméga ==

=== Preuves de problèmes non résolus en mathématiques par un nombre Oméga ===
La connaissance d'un Oméga de Chaitin permettrait, en théorie, de résoudre certains problèmes en [[théorie des nombres]], dont certains non résolus à ce jour comme la [[conjecture de Goldbach]] et l'[[hypothèse de Riemann]]<ref>{{CoverThomas06}}.</ref>.

Par exemple, la conjecture de Goldbach affirme que tout nombre pair plus grand que 2 est la somme de deux nombres premiers. Pour prouver cette conjecture à l'aide d'un nombre Oméga, il s'agirait de réaliser un programme qui recherche la décomposition de tous les nombres pairs en somme de deux nombres premiers. Pour un nombre pair donné, il est possible pour un programme de déterminer si la conjecture est vraie ou fausse en un temps fini (soit en trouvant la somme, soit en épuisant toutes les possibilités sans en trouver, ce qui serait un [[contre-exemple]] à la conjecture). Si le programme trouve un contre-exemple, il s'arrête, sinon il continue de chercher un contre-exemple à l'infini.

Donc : si la conjecture de Goldbach est vraie, le programme ne s'arrête pas, si elle est fausse, le programme s'arrête (en retournant un contre-exemple).

En sachant si ce programme se termine ou non en utilisant le nombre Oméga, on pourrait donc savoir avec certitude que la conjecture est vraie ou fausse.

De manière générale, les problèmes mathématiques dont la solution est potentiellement contenue dans un Oméga de Chaitin sont les problèmes ''réfutables en un temps fini'', c'est-à-dire pour lesquels un programme est en mesure de s'arrêter avec un contre-exemple en un temps fini. Tous les problèmes mathématiques ne sont pas réfutables en un temps fini, notamment :
* Est-ce que [[Pi|{{math|π}}]] est un [[nombre normal]] ?
* Existe-t-il une infinité de [[nombres premiers jumeaux]] ?
* Le [[problème P ≟ NP]].

ne sont ''pas'' réfutables en un temps fini, et leur solution n'est ''pas'' contenue dans un nombre Oméga<ref group="Li Vitanyi">p. 192.</ref>. On peut cependant remarquer que pour une axiomatique donnée (le plus souvent [[Théorie des ensembles de Zermelo-Fraenkel|ZFC]]), ces questions peuvent être considérées comme des affirmations susceptibles d'être démontrées, réfutées, ou [[Décidabilité|indécidables]] ; un nombre Oméga permet donc, pour une proposition ''P'' donnée, de savoir ce qu'il en est des deux machines de Turing énumérant tous les théorèmes et s'arrêtant respectivement si ''P''  en est un ou si sa négation en est un{{Référence souhaitée|date=16 septembre 2021}}.

Cependant, tout cela reste théorique. La méthode pour restituer les machines qui s'arrêtent à partir d'un nombre Oméga (autrement dit, pour « décompresser » un nombre Oméga, voir [[#Détermination de l'arrêt des programmes à partir du nombre Oméga|Détermination des programmes qui s'arrêtent à partir du nombre Oméga]]) est si longue qu'elle est inapplicable en pratique<ref name="TAGT">{{en}} G. J. Chaitin, ''Thinking about Gödel and Turing. Essays on Complexity'', World Scientific, 2007, p. 158-159.</ref>. En effet, il est nécessaire d'attendre que tous les programmes qui doivent s'arrêter s'arrêtent avant de connaitre le statut de chaque programme<ref name="TAGT" />. Comme il existe jusqu'à 2{{exp|N}} programmes de longueur N bits, qu'un programme individuel peut théoriquement s'arrêter au terme d'un temps arbitrairement long, et que l'ordre de grandeur de N pour les problèmes mathématiques intéressants est de l'ordre du millier<ref>[http://www.cs.auckland.ac.nz/~chaitin/whatis.pdf C. Calude et G. Chaitin ''What is... a Halting Probability''], p. 3.Pour une certaine machine de Turing, il suffit de connaitre les 7780 premiers bits de Oméga pour résoudre l'[[hypothèse de Riemann]].</ref>, il serait nécessaire d'attendre l'arrêt de <math>2^{1000} \simeq 10^{301}</math> programmes approximativement, parmi lesquels — plausiblement pour cette classe de programmes — le [[castor affairé]], dont le [[temps d'arrêt]] est lui-même incommensurablement long<ref>A titre indicatif, le [[Castor affairé#6 états|castor affairé d'une machine à seulement 6 états]] s'arrête au terme de {{formatnum:7412}}{{x10|36534}} pas.</ref>.

=== Calculabilité d'un nombre Oméga ===

Un nombre Oméga n'est pas [[calculabilité|calculable]], car il est aléatoire : aucun [[algorithme]] qui ne contient pas déjà le nombre en lui-même ne peut donner de manière certaine et dans un temps fini les N premiers bits d'un nombre Oméga. Cependant, le statut de ces nombres vis-à-vis de la calculabilité n'est pas trivial et mérite quelques précisions.

Un nombre Oméga n'est pas un nombre calculable, mais est un nombre ''approchable''<ref>Terminologie française employée par [[Delahaye|J.P. Delahaye]], en anglais ''computably enumerable.''</ref>. Cela signifie qu'il existe une séquence ''calculable'' et jamais décroissante de [[nombre rationnel|rationnels]] qui converge vers ce nombre<ref group="Calude">Chapitre 3.</ref>. C'est précisément cette caractéristique qui est mise en œuvre dans la [[#Détermination de l'arrêt des programmes à partir du nombre Oméga|« décompression » d'un nombre Oméga]], pour calculer une approximation de plus en plus précise d'un nombre Oméga (puisqu'on stoppe la décompression quand l'approximation égale le nombre Oméga).

Le problème est que, même si cette séquence est convergente, on n'a aucun moyen de savoir (cela est non calculable) quels bits du nombre Oméga ou même combien de bits seront exacts au terme de combien de temps. De plus, il a été démontré que la convergence vers un nombre Oméga par une séquence approchante est plus lente que n'importe quelle autre séquence convergente calculable<ref>{{Information, complexité et hasard|passage=88}}.</ref>. Même si une séquence approchante calculable existe, elle ne peut donc être utilisée pour calculer en pratique, et même en théorie, un nombre Oméga, qui reste de ce fait bel et bien non-calculable.

Il peut paraître dès lors paradoxal de constater que la valeur exacte des N premier bits de nombres Oméga ont été déterminés pour certaines machines de Turing universelles<ref group="Calude">''0000001000000100000110001000011010001111110010111011101000010000'' sont les 64 premiers bits d'un nombre Oméga.</ref>. Mais cela ne contredit pas les résultats précédents pour la raison suivante : la détermination de ces bits utilise un mélange de calcul et de raisonnements mathématiques, pour prouver que certains programmes ne s'arrêtent pas ou ne peuvent contribuer significativement à la somme finale. Le raisonnement mathématique étant une sorte de calcul, cette constatation ne semble pas faire avancer le paradoxe.

Seulement, il a été prouvé qu'un [[système formel]] mathématique (utilisé pour les raisonnements mathématiques, comme [[ZFC]] par exemple) fondé sur des [[axiome]]s qui représentent N bits d'information, ne pourra jamais déterminer plus de N+O(1) bits d'un nombre Oméga par des raisonnements mathématiques<ref group="Chaitin AIT">Theorem C, p. 210.</ref> (le nombre exact de bits que peut déterminer la théorie est incalculable). On ''peut'' donc déterminer un certain nombre de bits d'un nombre Oméga, mais un nombre ''fini'', incalculable, et d'autant plus faible que le système formel utilisé pour les raisonnements est élégant, et fondé sur un nombre le plus petit possible d'axiomes<ref group="Calude">Théorème 4.2.</ref>.

=== Nombre Oméga et incomplétude des mathématiques ===

Un nombre Oméga pose un défi à toute théorie, à tout [[système formel]], mathématique. Chaque bit d'un nombre Oméga représente, indépendamment des problèmes plus profonds qu'il peut résoudre, un [[théorème]] mathématique simple :
{{Théorème|nom = Théorème Oméga N|énoncé = Le N-ième bit d'un nombre Oméga est 1.}}
Chacun de ces théorèmes est soit vrai soit faux dans l'absolu. Le N-ième bit possède une valeur déterminée et univoque, même si elle ne peut pas être calculée : les machines de Turing qui contribuent à la détermination de ce bit s'arrêtent ou bien ne s'arrêtent pas dans l'absolu.

De plus, un nombre Oméga étant incompressible, l'infinité des théorèmes « Oméga N » sont autant de problèmes indépendants à résoudre pour une théorie mathématique. La [[complexité de Kolmogorov|complexité]] de tous les théorèmes mathématiques est infinie.

En 1931, [[Kurt Gödel]] a démontré l'incomplétude des théories mathématiques par le célèbre [[Théorèmes d'incomplétude de Gödel|théorème d'incomplétude de Gödel]] : il existe dans toute théorie mathématique suffisamment puissante, des énoncés qui ne sont pas démontrables et dont la négation n'est pas non plus démontrable. Ce sont des énoncés [[Décidabilité|indécidables]].

Les nombres Oméga apportent un éclairage complémentaire au théorème d'incomplétude de Gödel. Si l'on ne fait pas appel à la théorie algorithmique de l'information, la portée du théorème de Gödel n'est pas claire : Combien de théorèmes sont indécidables ? Est-ce l'exception ou la règle ? Les théorèmes indécidables se limitent-ils aux théorèmes « diagonaux » incontournables, ou sont-ils beaucoup plus répandus ? Est-il nécessaire d'augmenter le nombre d'axiomes pour diminuer le nombre de problèmes indécidables ? Quelle est la relation entre le nombre d'axiomes et le nombre de théorèmes indécidables ?

La théorie algorithmique de l'information et les nombres Oméga apportent des éléments de réponse à ces questions. En effet, selon la théorie algorithmique de l'information :
# Le nombre de problèmes (de théorèmes) ''indépendants'' (qui ne dérivent pas les uns des autres) à résoudre par les théories mathématiques est infini (il y a, au moins, les théorèmes « Oméga N »). Pratiquement tous les théorèmes « Oméga N » sont indécidables pour un système formel type ZFC<ref group="Calude">Théorème 4.3.</ref> ;
# La complexité des théorèmes résolus par une théorie mathématique est limitée par la complexité de l'ensemble de ses axiomes. Il s'agit du {{lien|fr=théorème d'incomplétude de Chaitin|trad=Kolmogorov_complexity#Chaitin.27s_incompleteness_theorem}} ;
# Donc le seul moyen de diminuer le nombre de problèmes indécidables est d'augmenter le nombre d'axiomes. Le nombre d'axiomes nécessaires pour résoudre les théorèmes « Oméga N » tend vers l'infini.

Selon ce point de vue, le théorème de Gödel a un impact très important sur la complétude des mathématiques : de très nombreux théorèmes, quasiment tous, sont indécidables. Les théorèmes vrais et démontrables sont un [[ensemble nulle part dense|ensemble rare]] parmi l'ensemble des théorèmes vrais<ref name="pls375">{{Presque tout est indécidable ! (Delahaye)}}.</ref>.

Mais on ne sait pas si des théorèmes « intéressants » des mathématiques ont une grande complexité (dans ce cas, ils seraient hors d'atteinte d'un système formel ayant trop peu d'axiomes), ou une complexité en définitive faible, ce qui est tout à fait possible<ref>La démonstration du [[dernier théorème de Fermat]] par [[Andrew Wiles]], bien que faisant plus de 100 pages de long, a une complexité faible au sens de la théorie algorithmique de l'information, car elle se réduit en définitive aux axiomes sur lesquels elle est fondée.</ref>. De plus, on pourrait arguer du fait que les théorèmes « Oméga N » sont des théorèmes artificiels, concernant un nombre spécialement construit pour être paradoxal, et ne sont pas représentatifs des véritables mathématiques.

Mais on peut démontrer qu'il existe une [[équation diophantienne]] <math>A(n,x_1,x_2,...,x_m)=0</math>, associé à un nombre Oméga, telle qu'elle admet pour solutions un ensemble ''fini'' de m-uplets <math>(x_1,x_2,...,x_m)</math> si le théorème « Oméga n » est vrai, et un ensemble ''infini'' de m-uplets <math>(x_1,x_2,...,x_m)</math> si le théorème « Oméga n » est faux pour ce nombre Oméga<ref group="Li Vitanyi">Lemme 3.7.1.</ref>.

En posant les choses de cette manière, les théorèmes « Oméga N » ne sont plus des théorèmes artificiels concernant un nombre étrange, mais d'authentiques problèmes mathématiques s'intéressant au nombre de solutions d'une équation.

=== Propriétés des nombres Ω ===

Les nombres Ω présentent maintes propriétés intéressantes et surprenantes.
* Un nombre Ω n'est pas calculable au sens de Turing : s'il l'était, on pourrait déterminer le [[problème de l'arrêt]].
* Un nombre Ω est transcendant, puisqu'il n'est pas calculable, et son développement binaire, décimal ou dans n'importe quelle base, est donc infini non périodique.
* Le produit de deux nombres Ω est un autre nombre Ω (associé à une autre machine universelle), de même que la somme de deux nombres Ω si elle est strictement comprise entre 0 et 1, et toute suite calculable extraite des décimales d'un nombre Ω (comme une décimale sur deux, ou celles de rang premier) est un autre nombre Ω.
* Un nombre Ω est un [[nombre normal]] (donc un [[nombre univers]] en toute base) : dans toute base de numération, ses décimales sont équiréparties, et toute suite finie de chiffres se trouve quelque part dans son expression dans cette base (dans tout nombre Ω écrit en binaire, il y a par exemple une suite d'un milliard de 0 successifs)<ref>J.-P. Delayahe, ''Complexités'', Belin, 2006, p. 135.</ref>.
* Pour une [[théorie axiomatique]] récursivement axiomatisable qui permet d'interpréter l'arithmétique, par exemple l'arithmétique de Peano ou la [[théorie des ensembles]], et sous une hypothèse de cohérence plus forte que la cohérence simple<ref>La 1-cohérence : toutes les formules arithmétiques Σ<sub>1</sub><sup style="position:relative; left:-1.2ex;bottom:.2ex;">0</sup> qui y sont démontrables sont vraies.</ref>, il existe un rang à partir duquel, bien qu'un des énoncés « le bit suivant du développement binaire est 0 » ou « le bit suivant du développement binaire est 1 » (en binaire) soit vrai, il est impossible de démontrer lequel des deux l'est, c'est-à-dire qu'ils sont indécidables dans la théorie en question. Solovay a renforcé ce résultat, en modifiant astucieusement une fonction universelle de Chaitin, en fonction d'une théorie donnée (vérifiant les mêmes hypothèses), pour exhiber un nombre Ω, qui dépend donc de cette théorie, et dont il est impossible de décider un seul chiffre dans celle-ci<ref>{{en}} R. M. Solovay, « [http://www.cs.auckland.ac.nz/CDMTCS/researchreports/104robert.pdf A version of Ω for which ZFC can not predict a single bit] », in ''Finite Versus Infinite - Contributions to an Eternal Dilemma'', C.S. Calude, G. Paun (eds.), Springer-Verlag, London, 2000.</ref>.

== Démonstration formelle de la formule ==
{{section à sourcer|date=août 2013}}
=== Les programmes auto-délimités ===

La définition d'une probabilité d'arrêt suppose qu'aucun programme ne résulte de l'extension d'un autre.

On considère une fonction ''F'' à deux arguments. ''F'' est dite ''universelle'' si pour toute fonction calculable ''f'' d'une seule variable ''x'' il y a une constante ''p'' telle que pour tout ''x'', ''F''(''p'',''x'') = ''f''(''x'') ; en d'autres mots, ''F'' peut être utilisée pour simuler n'importe quelle fonction calculable d'une seule variable. ''p'' représente un programme pour ''f'', et ''F'' représente un émulateur qui exécute ce programme ; pour chaque ''p'', ''f''(''x'') = ''F''(''p'',''x'') est calculable.

Le ''domaine'' de ''F'' est l'ensemble de tous les programmes ''p'' tels que ''F''(''p'',''x'') soit définie pour au moins une valeur de ''x''. Selon la convention ci-dessus, il n'existe pas dans le domaine deux programmes différents ''p''<sub>1</sub> et ''p''<sub>2</sub> tels que l'un d'eux soit une extension de l'autre : on dit que ''F'' est sans préfixe.

Ceci revient à parler de la machine universelle (machine de Turing) correspondant à ''F'' dont les programmes ont une séquence de fin.

=== Interprétation comme probabilité ===

On considère l'[[espace de Cantor]] formé de toutes les suites infinies de '''0''' et de '''1'''. Une probabilité d'arrêt peut être interprétée comme la [[théorie de la mesure|mesure]] d'un certain sous-ensemble de cet espace.

La mesure probabiliste dans cet espace est définie de façon que pour toute chaîne ''x'' l'ensemble des suites qui commencent par ''x'' mesure '''2'''<sup>-|''x''|</sup>. Ceci entraîne que pour tout entier naturel ''n'' l'ensemble des suites ''f'' de l'espace de Cantor telles que ''f''(''n'') = '''1''' mesure '''0,5''' et que l'ensemble des suites dont le ''n''-ième élément est '''0''' mesure aussi '''0,5'''.

Soit {{math|''F''}} une fonction universelle calculable sans préfixe telle que décrite plus haut. Le domaine {{math|''P''}} de {{math|''F''}} est un [[ensemble infini]] de chaînes :
:<math>P = \{p_1,p_2,\ldots\}.</math>

Chaque <math>p_i</math> détermine un sous-ensemble <math>S_i</math> de l'espace de Cantor, ce sous-ensemble contient toutes les suites qui commencent par <math>p_i</math>.
Les <math>S_i</math> étant disjoints — puisque par hypothèse aucun des <math>p_i</math> n'est inclus dans un autre — la somme :
:<math>\sum_{p \in P} 2^{-|p|}</math>

représente la mesure de {{math|''P''}}.

De cette façon, Ω<sub>''F''</sub> est la probabilité qu'une suite de l'espace de Cantor choisie au hasard commence par une chaîne qui soit un élément du domaine de <math>\quad F</math>. C'est pour cette raison que Ω<sub>''F''</sub> s'appelle la probabilité d'arrêt.

== Bibliographie ==
* Gregory Chaitin, ''Hasard et complexité en mathématiques, la quête de Ω'', Flammarion, {{date-|janvier 2007}} {{ISBN|2082105687}}.
*{{en}} Gregory Chaitin, « The halting probability Omega : Irreductible complexity in pure mathematics », ''Milan J. Math.'', vol. 75, 2007, p. 291-304, {{DOI|10.1007/s00032-006-0064-2}}, {{arxiv2|math/0611740}} :
{{Références|groupe="Chaitin 2007"}}
*{{en}} Ming Li et [[Paul Vitanyi]], ''An Introduction to Kolmogorov Complexity and its Applications'', Springer, 2008 :
{{Références|groupe="Li Vitanyi"}}
*{{en}} [[Cristian S. Calude]], Michael J. Dinneen et Chi-Kou Shu, ''[http://www.expmath.org/expmath/volumes/11/11.3/Calude361_370.pdf Computing a Glimpse of Randomness]'' :
{{Références|groupe="Calude"}}
*{{en}} Gregory Chaitin, ''[http://www.umcs.maine.edu/~chaitin/cup.pdf Algorithmic Information Theory]'', {{3e}} éd., [[Cambridge University Press]], 2003 :
{{Références|groupe="Chaitin AIT"}}

== Notes et références ==
{{Références}}

== Voir aussi ==
===Articles connexes===
* [[Suite de Specker]]

===Lien externe===
{{MathWorld|nom_url=ChaitinsConstant|titre=Chaitin's Constant}}

{{portail|informatique théorique}}

[[Catégorie:Théorie algorithmique de l'information]]
[[Catégorie:Calculabilité]]
[[Catégorie:Nombre transcendant]]
[[Catégorie:Nombre remarquable]]
[[Catégorie:Nombre aléatoire]]