Oméga de Chaitin

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques et l’informatique.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Dans le sous-domaine de l’informatique qu’est la théorie algorithmique de l’information, la constante Oméga de Chaitin ou la probabilité d’arrêt est un nombre réel défini par Grégory Chaitin. Ce nombre décrit la probabilité qu’un programme informatique généré aléatoirement à partir d’un modèle de calcul ou d’un langage de programmation donné s’arrêtera.

G. Chaitin a démontré que c'est un nombre normal qui n'est pas calculable au sens de Turing, et, ce qui est plus étonnant encore, que dans un système axiomatique donné, il n'est possible de déterminer la valeur que d'un petit nombre de ses décimales, les valeurs des décimales suivantes pouvant être choisies arbitrairement comme de nouveaux axiomes.^{[réf. nécessaire]}

Sommaire

1 Contexte
2 Définition de la probabilité d'arrêt
3 Interprétation comme probabilité
4 Représentation de l'expérience
5 Utilisation de la constante de Chaitin en théorie des nombres
6 Propriétés des nombres Ω
7 Notes et références
8 Voir aussi

[modifier] Contexte

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

Article détaillé : Problème de l'arrêt.

On considère une fonction F a 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 éxé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₁ et p₂ 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.

[modifier] Définition de la probabilité d'arrêt

Soit $\quad P_F$ le domaine d'une fonction universelle $\quad F$ répondant aux conditions ci-dessus. Alors :

$\Omega_F = \sum_{p \in P_F} 2^{-|p|}$ ,

où $| p |$ est la longueur de p.

Bien qu'il y ait plusieurs probabilités d'arrêt dépendant du code utilisé pour générer les programmes, on a l'habitude d'utiliser la lettre Ω pour désigner cette probabilité, comme si elle était unique. Quand aucun code particulier n'est spécifié, on parle plutôt de construction de Chaitin.

[modifier] 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 mesure d'un certain sous-ensemble de cet espace.

La mesure probabiliste dans cet espace est définie de façon à ce que pour toute chaîne x l'ensemble des suites qui commencent par x mesure 2^-|x|. 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 $\quad F$ une fonction universelle calculable sans préfixe telle que décrite plus haut. Le domaine $\quad P$ de $\quad F$ est un ensemble infini de chaînes :

$\quad P = \{p_1,p_2,\ldots\}$ .

Chaque $\quad p_i$ détermine un sous-ensemble $S i$ de l'espace de Cantor, ce sous-ensemble contient toute les suites qui commencent par $\quad p_i$ . Les $S i$ étant disjoints - puisque par hypothèse aucun des $\quad p_i$ n'est inclus dans un autre - la somme :

$\sum_{p \in P} 2^{-|p|}$

représente la mesure de $\quad P$ .

De cette façon, Ω_F 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 $\quad F$ . C'est pour cette raison que Ω_F s'appelle la "probabilité d'arrêt".

[modifier] Représentation de l'expérience

La constante Ω est définie à partir de la probabilité d'arrêt d'un programme de la façon suivante : on effectue une série de tirages aléatoires (de 0 ou de 1 si on écrit en binaire) jusqu'à obtenir la séquence de fin correspondant à la machine universelle considérée ; on teste alors le programme obtenu. On considère qu'il y a échec quand on n'obtient jamais la séquence de fin dans les tirages aléatoires ou quand le programme ne s'arrête jamais.

[modifier] Utilisation de la constante de Chaitin en théorie des nombres

La constante de Chaitin pourrait être employée, dans l'idéal, pour résoudre certains problèmes en théorie des nombres, dont la conjecture de Goldbach et l' hypothèse de Riemann.^[1] La conjecture de Goldbach dit que tout nombre pair plus grand que 2 est la somme de deux nombres premiers. Il s'agirait, étant donné un nombre pair donné, de lancer une recherche par ordinateur pour trouver les deux nombres premiers correspondants. Si la conjecture de Goldbach est vraie, le programme incrémente au nombre pair suivant et poursuit la recherche. S'il n'y a pas de tels nombres premiers, le programme s'arrête, un contre-exemple a été trouvé et la conjecture de Goldbach a été réfutée. Si la longueur du programme p est de N bits, Oméga peut théoriquement être mise à contribution comme suit :

On exécute en parallèle tous les programmes longs de N+1 bits ou moins. Si p s'arrête, la conjecture de Goldbach est réfutée ; si par contre, il ne s'arrête pas alors que suffisamment d'autres programmes se sont arrêtés pour que la constante de Chaitin soit atteinte, alors il ne stoppera jamais et la conjecture de Goldbach est prouvée.

Cela suppose évidemment que l'expérimentateur ne soit pas limité en ressources et en temps, mais ce n'est pas l'objection principale. Ce qui se passe, c'est que la constante fonctionne en fait comme un oracle compressé, et qui contient une réponse au problème de l'arrêt pour toutes les machines de Turing ; on voit donc que cette constante est par essence incalculable...

[modifier] Propriétés des nombres Ω

Les nombres Ω présentent maintes propriétés intéressantes et surprenantes. Un nombre Ω est transcendant (inexistence d'une équation polynômiale à coefficients entiers dont il soit solution ; il est par conséquent irrationnel) et possède donc une infinité de décimales. 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 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-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). Les nombres Ω sont incalculables au sens de Turing, et une suite convergeant vers un nombre Ω a une vitesse de convergence infiniment lente : ainsi, existe un rang à partir duquel, bien qu'un des énoncés "la décimale suivante est un 0" et "la décimale suivante est un 1" (en binaire) soit vrai, il est impossible de déterminer lequel, ils sont indécidables. Solovay a même exhibé une classe de nombres Ω dont il est impossible de connaître un seul chiffre ! ^[2]

[modifier] Notes et références

↑ Thomas M. Cover et Joy A. Thomas, Elements of Information Theory, 2ème édition, Wiley-Interscience, 2006
↑ R. M. Solovay, “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. P˘aun (eds.), Springer-Verlag, London, 2000