thumb|right|upright=1.2|Un nombre Oméga de Chaitin est une suite de bits 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 aléatoire et de ne pas être 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 Cristian Calude, Information and Randomness: An Algorithmic Perspective, Springer, 1994, p. 181..
Techniquement, il est défini comme étant la probabilité qu’un programme auto-délimité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)., 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èmes ou de conjectures mathématiques, dont certains encore non résolus à ce jour comme l'hypothèse de Riemann.
Ces nombres apportent un éclairage sur l'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 le domaine d'une machine de Turing universelle , c'est-à-dire l'ensemble des programmes auto-délimités pouvant être exécutés par qui s'arrêtent.
Par définition :
où est la longueur de .
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 et qu'il soit un qui doit Émile Borel, Les nombres inaccessibles, Gauthier-Villars, 1951, , .. 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. ChaitinParagraphe : Borel: Know-it-all and unnameable reals.), résumant les réponses à toutes les questions formulables dans un langage donné, auxquelles on peut répondre par oui ou par nonRevue de Métaphysique et de Morale, 1927, vol. 34, n° , p. 271-275, lettre de É. Borel.. Cette liste de questions constitue une liste infinie, mais 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 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).
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êtParagraphe : What is the halting probability Ω ?), est hautement redondant et compressible. Or, une des définitions d'un nombre aléatoire est précisément d'être incompressibleVoir l'article « Suite aléatoire ».. 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 right|upright=0.8|thumb|Représentation d'un ensemble de programmes auto-délimités sous forme d'un arbre binaire.Ici, nous avons quatre programmes possibles, correspondant aux quatre feuilles de l'arbre : "01(00)", "011(00)", "0101(00)", et "101(00)"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 log2(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 2N 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 2N 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 de taille par . 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 ( est l'ensemble de définition de la machine , c'est-à-dire l'ensemble de tous les programmes qui retournent un résultat et par conséquent s'arrêtent ; est la longueur en bits du programme ) :
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-|p|. 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és de Kraft.
Détermination de l'arrêt des programmes à partir du nombre Oméga