« Oméga de Chaitin » : différence entre les versions
Contenu supprimé Contenu ajouté
image inutile |
m Annulation de la modification de Kephir (d)inutile ? À discuter en pdd |
||
Ligne 1 :
[[File:OmegaChaitin.png|thumb|right|upright=1.2|Un nombre Oméga de Chaitin est une suite de [[bit]]s 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''' est un [[nombre réel]] défini comme étant la [[probabilité]] qu’un [[fonction partielle récursive|programme]] auto-délimité<ref>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).</ref>, généré aléatoirement, finisse par s'arrêter.
Ligne 164 ⟶ 166 :
* 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)<ref>J.-P. Delayahe, ''Complexités'', Belin, 2006, p. 135.</ref>.
* 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<ref>La 1-cohérence : toutes les formules Σ<sub>1</sub><sup style="position:relative; left:-1.2ex;bottom:.2ex;">0</sup> vraies de l'arithmétique sont démontrables.</ref>, 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<ref>{{en}} R. M. Solovay, «
== Démonstration formelle de la formule ==
| |||