Oméga de Chaitin

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 programme d'une machine de Turing universelle donnée.

En théorie algorithmique de l'information, une constante Oméga de Chaitin est un nombre réel défini comme étant la probabilité qu’un programme informatique auto-délimité, dont chaque bit est généré aléatoirement, finira par s'arrêter.

Ces programmes sont associé à une machine de Turing universelle, ou à un modèle de calcul donné. Il existe donc une infinité de constantes de Chaitin, chacune associée à un modèle de calcul.

Cette définition permet de caractériser de manière univoque et mathématiquement précise un nombre, qui possède la particularité d'être aléatoire et d'être non-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 pouvant être désigné autrement qu'en écrivant cette suite in-extenso^[1].

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.

Ce nombre apporte enfin un éclairage sur l'incomplétude des mathématiques, mis au jour par le célèbre théorème de Gödel, et d'apporter des éléments d'appréciation en ce qui concerne sa signification et sa portée.

Ces nombres ont été définis et étudiés par Gregory Chaitin.

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

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

Alors :

,

où | p | est la longueur de 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 Omega 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 excessivement difficile d'en exhiber, ou d'en décrire, un.

En effet, pour exhiber un nombre, il faut soit le nommer ou 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 a 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 Omega 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é profondes et intéressantes. A ce titre, il constitue un des éléments très important de la théorie algorithmique de l'information.

Origine, définition et construction du nombre Omega

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 « deux mathématiciens, s’ils en parlent entre eux, soient certains qu’ils parlent du même nombre » et qu'il soit un « véritable "être" mathématique » qui doit « 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) »^[2]. 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^{[Chaitin 2007 1]}), résumant les réponses à toutes les questions formulables dans un langage donné, auxquelles on peut répondre par oui ou par non^[3]. 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 Nième décimale binaire est la réponse à la Nième question.

Ces deux idées contiennent les germes du nombre Oméga. Chaitin, qui connait très bien l'œuvre de Borel, reconnait 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 on recycle l'idée du "nombre qui sait tout" pour définir un nombre dont la Nième décimale répond au problème de l'arrêt pour le Niè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 non calculable, 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 Omega, 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^{[Chaitin 2007 2]}), est hautement redondant et compressible. Or, une des définitions d'un nombre aléatoire est précisément d'être incompressible^[4]. 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

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 connaitre 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 on connait 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^N programmes et de s'arrêter quand P programmes seront arrêtés (ce qui arrivera certainement). On est alors sûr que les programmes restants ne s'arrêteront jamais. On connait 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^N 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 p de taille |p| par 2 ^{− | 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 (P_U est l'ensemble de définition de la machine U, c'est-à-dire l'ensemble de tous les programmes qui retournent un résultat et par conséquent s'arrêtent; |p| est la longueur en bits du programme p) :

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 "juste poids" à chaque nœud terminal, on démontre que l'on arrive au plus à la somme de "1" si on prend en compte tous les nœuds. Cette propriété est démontrée par les inégalités de Kraft (en).

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 Ω_n l'approximation d'un nombre Oméga consistant à prendre les N premiers bits de ce nombre Oméga. Comment, étant donné ce nombre Ω_n, déterminer les programmes de longueur inférieure à N bits qui s'arrêtent ou non ?

L'inégalité est évidente.

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 Ω_n à chaque arrêt d'une machine, en ajoutant 2 ^{− l}, l étant la longueur du programme s'étant arrêté, à l'approximation précédente.

Dès que l'approximation de Ω_n atteint une valeur telle que l'ajout du poids d'un programme quelconque non encore terminé rendrait l'approximation supérieure ou égale à Ω_n + 2 ^{− n}, 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 : Ω_n^{[Li Vitanyi 1]}.

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 ω_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 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 ω_n dans son programme, il s'ensuit que TAILLE(COMPLEXE) = TAILLE(ω_n) + O(1) > N^{[Li Vitanyi 2]}.

Le plus petit programme pour calculer les N premiers bits de Ω a une taille supérieure à N − O(1) , ce qui est la caractéristique d'un 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^[5].

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.

Cependant, tout cela reste théorique. En pratique, 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 des programmes qui s'arrêtent à partir du nombre Oméga) est si longue qu'elle est inapplicable en pratique. 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. Comme il existe jusqu'à 2^N programmes de longueur N bits, et 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, il serait nécessaire d'attendre l'arrêt de jusqu'à programmes. Même si la moyenne des temps des programmes qui s'arrêtent est de l'ordre de la nanoseconde (ce qui est déjà en soi inenvisageable), l'âge de l'univers n'y suffirait pas.

Calculabilité d'un nombre Oméga

Un nombre Oméga n'est pas 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^[6]. Cela signifie qu'il existe une séquence calculable et jamais décroissante de rationnels qui converge vers ce nombre^{[Calude 1]}. C'est précisément cette caractéristique qui est mise en œuvre dans la "décompression" d'un nombre Oméga, pour calculer une approximation de plus en plus précise d'un nombre Oméga (puisque 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. 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^{[Calude 2]}. 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 axiomes 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^{[Chaitin AIT 1]} (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^{[Calude 3]}.

Nombre Oméga et l'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 :

Chacun de ces théorèmes est soit vrai soit faux dans l'absolu. Le Niè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é des mathématiques pures est infinie.

En 1931, Kurt Gödel a démontré l'incomplétude des théories mathématiques par le fameux 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 dit indécidables.

Les nombres Oméga apportent un éclairage complémentaire au théorème d'incomplétude de Gödel. Si 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 :

1. 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^{[Calude 4]}.
2. La complexité des théorèmes résolus par une théorie mathématique est limité par la complexité de l'ensemble de ses axiomes. Il s'agit du théorème d'incomplétude de Chaitin (en).
3. 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 rare parmi l'ensemble des théorèmes vrais^[7].

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^[8]. 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 A(n,x₁,x₂,...,x_m) = 0, associé à un nombre Oméga, telle qu'elle admet pour solutions un ensemble fini de m-uplets (x₁,x₂,...,x_m) si le théorème "Oméga n" est vrai, et un ensemble infini de m-uplets (x₁,x₂,...,x_m) si le théorème "Oméga n" est faux pour ce nombre Oméga^{[Li Vitanyi 3]}.

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.
• 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 et 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)^[9].
• 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^[10], 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^[11].

Démonstration formelle de la formule

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₁ 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.

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 une fonction universelle calculable sans préfixe telle que décrite plus haut. Le domaine de est un ensemble infini de chaînes :

.

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

représente la mesure de .

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 . C'est pour cette raison que Ω_F s'appelle la "probabilité" d'arrêt.

Bibliographie

• Gregory Chaitin, Hasard et complexité en mathématiques, la quête de Ω, Flammarion, Janvier 2007, ISBN 2082105687.
• Gregory Chaitin The halting probability Omega : Irreductible complexity in pure mathematics Milan Journal of Mathematics 2007 :

1. ↑ Paragraphe : Borel: Know-it-all and unnameable reals
2. ↑ Paragraphe : What is the halting probability Ω ?

• Ming Li, Paul Vitanyi An introduction to Kolmogorov complexity and its applications Springer 2008 :

1. ↑ Lemme 3.6.1
2. ↑ Lemme 3.6.2
3. ↑ Lemme 3.7.1

• Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu. Computing a Glimpse of Randomness :

1. ↑ Chapitre 3.
2. ↑ 0000001000000100000110001000011010001111110010111011101000010000 sont les 64 premiers bits d'un nombre Oméga
3. ↑ Théorème 4.2
4. ↑ Théorème 4.3

• Gregory Chaitin, Algorithmic Information Theory, 3rd printing Cambridge University Press, 2003 :

1. ↑ Theorem C, p. 210

Notes et références

Voir aussi

• Problème de l'arrêt
• Suite de Specker
• Suite aléatoire

• Portail de l'informatique théorique