Impromptu de Cyril Melac - comité de septembre 2024
Contact : cmelac@zaclys.net
C’est un des dix-huit thèmes du livre de Reda Benkirane dédié à la complexité, au principe d’émergence et à la théorie du chaos.
Voici une présentation succincte de cet Ω, tirée d’un article de Jean-Claude Simard, Université du Québec à Montréal
[…
Gregory Chaitin (1947-) mathématicien et informaticien américain est considéré comme le Gödel de l’informatique.
Il existe une infinité de fonctions pour lesquelles il n’existe aucun algorithme. Un exemple classique de ces fonctions est le célèbre problème de l’arrêt, lié à l’entscheidungsproblem de Hilbert. Selon Chaitin, « aucun jeu d’axiomes ne nous permettra jamais de déduire qu’un programme s’arrêtera ou non».
À ce propos, il a introduit une constante Ω, le nombre Oméga. Il est assez complexe, mais en termes simples, on peut le définir comme la probabilité qu’un programme finisse par s’arrêter. Précisons que le programme en question doit être généré de manière aléatoire et que sa fin doit être prévue et codée dans le programme lui-même ; on dit alors qu’il est auto-délimité. Cette constante Ω, qui formalise le problème de l’arrêt, est un nombre réel transcendant, compris entre 0 et 1. Or, il présente une particularité très étonnante : tout en possédant une définition mathématique simple, il est incalculable. La suite de ses décimales ne peut être donnée par aucun algorithme.
…]
Cet autre lien, https://www.youtube.com/watch?v=LGYlT6DsfH8 , propose une vidéo sur Ω.