Oméga de Chaitin

Carte Commune · n° 281532

En théorie algorithmique de l'information, une constante Oméga de Chaitin (nombres définis et étudiés par Gregory Chaitin) caractérise de manière univoque et mathématiquement précise un nombre réel, qui possède la particularité d'être aléatoire et de ne pas être 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. Techniquement, il est défini comme étant la probabilité qu’un programme auto-délimité, généré aléatoirement, finisse par s'arrêter. Les programmes en question sont associés à une machine de Turing universelle ou à un modèle de calcul donné. Il existe donc une infinité de constantes de Chaitin, chacune associée soit à une machine de Turing universelle donnée, soit à un modèle de calcul. Cette définition permet également de coder, sous la forme la plus compacte possible, la solution du problème de l'arrêt...

Lire sur Wikipédia · Image Jean-Christophe BENOIST, CC BY 3.0