Oméga de Chaitin

Imaginez que l'on tire au hasard une suite de 0 et de 1, puis qu'une machine la lise comme un programme. Certains programmes finissent leur travail ; d'autres tournent sans fin. Oméga est la part de tous ces tirages qui conduisent à un arrêt. Le nombre est parfaitement défini, mais aucun algorithme ne peut en livrer les chiffres aussi loin qu'on le souhaite.

On fixe une machine de Turing universelle, notée U, dont les programmes binaires sont auto-délimités : aucun programme valide n'est le début d'un autre. Cette condition rend compatibles les poids probabilistes. La constante associée, notée Oméga avec l'indice U, additionne le poids de chaque programme p sur lequel U s'arrête. La longueur du programme p est notée |p|.

Chaque choix admissible de machine universelle donne sa propre constante ; il existe donc une infinité de constantes Oméga. Elles sont non calculables : une procédure générale ne peut pas produire arbitrairement leurs chiffres. Leur aléa algorithmique entraîne notamment leur normalité dans toute base et leur transcendance. Leurs chiffres encodent aussi des réponses au problème de l'arrêt, ce qui relie ces nombres aux limites formelles mises en lumière par les théorèmes d'incomplétude de Gödel.

Considérons une machine jouet, non universelle. Elle accepte quatre programmes auto-délimités : 0 et 110 s'arrêtent ; 10 et 111 bouclent. Un bit vaut 0 ou 1 avec la même probabilité, indépendamment des précédents. Les poids annoncés sont donc 1/2 pour 0, 1/4 pour 10, puis 1/8 pour chacun des programmes 110 et 111.

1. Conserver seulement les programmes qui s'arrêtent : 0 et 110.

2. Additionner leurs poids : $2^{-1}+2^{-3}=\frac{1}{2}+\frac{1}{8}=\frac{5}{8}2^\{-1\}+2^\{-3\}=\backslash frac\{1\}\{2\}+\backslash frac\{1\}\{8\}=\backslash frac\{5\}\{8\}$.

3. Le résultat est une probabilité d'arrêt de 5/8, soit 0,625 exactement. Le contrôle consiste à additionner les quatre poids : 1/2 + 1/4 + 1/8 + 1/8 = 1. Cette construction finie montre le mécanisme, mais son résultat n'est pas une constante de Chaitin, car la machine n'est pas universelle.

Pour raisonner sur l'arrêt des programmes, Oméga rassemble en un seul nombre les cas où une machine universelle termine. Si l'on veut décider l'arrêt d'un programme particulier, une analyse directe du programme reste préférable : Oméga n'est pas une table calculable que l'on pourrait consulter.

En théorie algorithmique de l'information, la constante sert d'exemple extrême d'un nombre défini par une règle courte dont les chiffres ne sont pourtant pas calculables à volonté. Pour étudier une suite effectivement calculable, on choisit plutôt une constante munie d'un algorithme de calcul.

Dans l'étude de l'incomplétude, les chiffres d'Oméga rendent concrète une limite de la preuve formelle. Le bon geste consiste à annoncer la machine universelle et le système formel considéré, car changer l'un ou l'autre change l'énoncé précis.

Le problème de l'arrêt. Il demande, pour un programme et une entrée donnés, si l'exécution finira. Oméga est au contraire un nombre associé à une machine universelle et à l'ensemble pondé de ses programmes. Une question oui ou non sur un programme relève du premier ; une probabilité globale relève du second.

Une probabilité empirique. Oméga n'est pas estimée en chronométrant un échantillon de programmes pendant un temps fixé. Un programme encore actif peut s'arrêter plus tard. L'absence d'arrêt observé n'est donc pas la preuve qu'il bouclera toujours.

Un nombre aléatoire tiré au hasard. Une constante Oméga est déterminée dès que la machine est fixée. Le hasard intervient dans la lecture probabiliste de ses programmes ; il ne signifie pas que la valeur change d'une expérience à l'autre.

Oublier la machine. Parler de « la » constante Oméga sans préciser le modèle masque une dépendance essentielle. Deux machines universelles admissibles peuvent produire deux valeurs différentes ; il faut donc noter la machine, par exemple avec l'indice U.

Confondre approximation et calcul complet. Exécuter des programmes fournit des contributions lorsqu'ils s'arrêtent, mais ceux qui tournent encore laissent une incertitude. Une somme partielle croissante n'autorise pas à annoncer le prochain chiffre comme définitif sans borne suffisante sur le reste.

Prendre le cas jouet pour une vraie constante de Chaitin. Dans l'exemple fini, le seuil exact vaut 5/8 et se calcule. Cette calculabilité signale justement que la machine n'est pas universelle ; l'exemple illustre la pondération, pas l'incalculabilité.

Lire « normal » comme « calculable ». La normalité décrit la fréquence des blocs de chiffres dans une base. Elle ne fournit aucun procédé pour engendrer ces chiffres ; Oméga peut donc être normale tout en restant non calculable.

La machine de Turing précise le modèle de calcul auquel chaque constante Oméga est attachée.

Les théorèmes d'incomplétude de Gödel éclairent la limite des systèmes formels que les chiffres d'Oméga rendent particulièrement concrète.

Un nombre normal permet d'approfondir la répartition des chiffres attribuée aux constantes Oméga dans toute base.

Un nombre transcendant situe Oméga parmi les réels qui ne satisfont aucune équation polynomiale non nulle à coefficients entiers.