Oméga de Solovay

Imaginez un nombre écrit en binaire, bit par bit. La non-calculabilité d'un oméga de Chaitin interdit un algorithme qui en donnerait des approximations aussi précises qu'on le souhaite ; elle ne dit pas, à elle seule, quels bits isolés une théorie peut démontrer. Ici, T désigne le cadre de règles et d'axiomes dans lequel on cherche des preuves, tandis que la machine universelle auto-délimitée U présente le nombre comme sa probabilité d'arrêt. Dans la construction de Solovay, T ne peut démontrer la valeur d'aucun bit de l'oméga ainsi présenté.

Le nombre reste pourtant défini. L'impossibilité porte ici sur les preuves disponibles dans T pour cette présentation par U, non sur l'existence du réel : une règle mathématique peut désigner exactement un nombre sans permettre à la théorie fixée d'en établir un bit.

Selon la définition retenue ici, l'expression « oméga de Solovay » désigne l'oméga d'une présentation particulière par une machine universelle auto-délimitée. C'est donc toujours un oméga de Chaitin : la probabilité d'arrêt de cette machine, un réel bien défini mais non calculable.

La propriété de Solovay est relative à un cadre précis. On fixe une théorie formelle T récursivement axiomatisable et 1-cohérente — ou, dans le cas de ZFC, supposée arithmétiquement saine — puis on construit en fonction de T une machine universelle auto-délimitée U. Dans le sens strict retenu ici, son oméga est dit de Solovay lorsque, pour tout rang n, T ne démontre ni que le n-ième bit du développement binaire de l'oméga de U vaut 0, ni qu'il vaut 1.

Cette propriété porte donc sur ce que T peut démontrer à propos d'une présentation de l'oméga par U ; ce n'est pas une propriété intrinsèque du réel pris seul. La non-calculabilité signifie seulement qu'aucun algorithme uniforme ne produit des approximations de précision arbitraire ; elle n'exclut pas, à elle seule, que des bits isolés soient démontrables. Robert Solovay a introduit cette construction dans les années 2000 au cours de travaux sur les omégas de Chaitin en théorie algorithmique de l'information.

Fixons une théorie formelle T satisfaisant les hypothèses de la construction. Le réel C est la probabilité d'arrêt d'une machine universelle auto-délimitée U_C, sans autre information. La machine universelle auto-délimitée U_S est, elle, construite relativement à T de sorte que, pour chaque rang n, T ne démontre ni que le n-ième bit de sa probabilité d'arrêt S vaut 0, ni qu'il vaut 1.

1. Pour C, la définition établit qu'il s'agit d'un oméga de Chaitin non calculable : aucun algorithme uniforme ne peut en fournir des approximations de précision arbitraire. Elle ne permet pas de conclure que T ne démontre la valeur d'aucun bit isolé.

2. Pour S, le critère est satisfait directement : l'hypothèse quantifie sur tous les rangs n et exclut dans T les deux preuves possibles de la valeur du n-ième bit. S est donc l'oméga d'une machine de Solovay relativement à T.

3. Puisque U_S est universelle et auto-délimitée, S est aussi un oméga de Chaitin. En revanche, les seules données sur U_C ne permettent pas de classer sa présentation comme solovayenne relativement à T. Le schéma d'inclusion représente ce sens unique : la propriété de Solovay implique le statut d'oméga de Chaitin, mais pas l'inverse.

Dans un texte de théorie algorithmique de l'information, la première vérification porte sur l'objet désigné : il doit s'agir de la probabilité d'arrêt d'une machine universelle auto-délimitée. Si le texte parle seulement d'un réel non calculable, la catégorie plus large des réels non calculables est préférable.

Devant une affirmation sur les chiffres, il faut distinguer deux questions. L'absence d'un algorithme uniforme donnant une précision arbitraire établit la non-calculabilité. La propriété de Solovay affirme autre chose : dans une théorie T fixée, aucune des propositions « le n-ième bit binaire vaut 0 » ou « il vaut 1 » n'est démontrable, quel que soit n.

Pour comparer deux descriptions, il faut donc repérer la machine U, la théorie T et le développement binaire concernés. Sans ces précisions, mieux vaut conserver l'appellation générale « oméga de Chaitin » : la même valeur réelle peut être présentée comme probabilité d'arrêt de machines différentes, et les bits que T peut démontrer dépendent de cette présentation.

Oméga de Chaitin. C'est la probabilité d'arrêt d'une machine universelle auto-délimitée. Sa non-calculabilité exclut un algorithme uniforme d'approximation arbitraire, mais ne dit pas quels bits isolés une théorie T peut démontrer ; sans propriété supplémentaire de la présentation par la machine U, on ne peut pas conclure au cas de Solovay.

Réel non calculable. Ce terme signifie qu'aucun algorithme ne fournit une précision arbitraire. Un réel peut être non calculable sans être une probabilité d'arrêt et donc sans appartenir à l'une des deux classes d'omégas.

Test de Solovay–Strassen. Malgré le nom de Robert Solovay, il s'agit d'un test probabiliste de primalité. Une mention de nombres premiers ou de symbole de Jacobi tranche en faveur de ce test, sans rapport avec les nombres oméga.

Prendre « aucun chiffre » au sens absolu. Le résultat porte sur les bits du développement binaire et sur leur démontrabilité dans une théorie formelle T fixée, pour une présentation par une machine U construite relativement à T. Sans T et U, l'énoncé est incomplet.

Confondre définition et preuve des bits. L'absence de valeur de bit démontrable dans T ne rend pas le nombre vague. Le symptôme de cette confusion est la phrase « le nombre n'existe pas puisque T n'en prouve aucun bit » ; il faut séparer la règle qui définit le réel des propositions que la théorie peut démontrer.

Renverser l'implication. L'oméga d'une machine de Solovay est un oméga de Chaitin, mais le seul label « oméga de Chaitin » ne suffit pas pour conclure que sa présentation est solovayenne relativement à T. Il faut vérifier la propriété de la machine U sur la démontrabilité de chaque bit.

L'article Oméga de Chaitin présente la classe englobante et relie ces réels à la probabilité d'arrêt.

La fiche complexité de Kolmogorov approfondit la mesure algorithmique qui éclaire l'absence de structure exploitable.

La machine de Turing fournit le modèle de calcul nécessaire pour situer les notions d'arrêt et de calculabilité.