Revue (et non résumé) de l’article « Presque tout est indécidable ! » Signé Jean-Paul DELAHAYE dans « Pour la SCIENCE » de Janvier 2009 (page 88).
Avant toute chose je veux dire que les critiques qui suivent sont faites en toute humilité tant je sais bien les difficultés de la vulgarisation scientifique, difficultés aggravées dans le cas des mathématiques et pire de la logique.
Je fais ces critiques volontairement sans avoir cherché des informations complémentaires, considérant qu’il devrait être auto-suffisant (sauf pour les détails techniques réservés aux spécialistes), et pour conserver une espèce de candeur à la lecture de cet article.
La question centrale traitée par l’article est « quels sont les liens entre l’incomplétude des systèmes mathématiques suffisamment évolués et le hasard », donc liens entre incapacité de démontrer et incapacité de prévoir. (Par « suffisamment évolués » il faut comprendre « contenant l’arithmétique »)
Premier lien : le théorème de Gödel permet d’affirmer que non seulement les systèmes mathématiques concernés ne sont pas complets, mais aussi que même si on ajoute, à l’aide d’un algorithme déterministe, une infinité d’axiomes, le résultat sera toujours une théorie incomplète. Les travaux de Levin ont montré que même si on ajoute une infinité d’axiomes par un processus probabiliste et non plus déterministe, le résultat sera toujours une théorie incomplète.
Critique : La question, qui me paraît centrale, de savoir pourquoi a-t-on pu penser qu’un processus probabiliste aurait pu changer le résultat de Gödel n’est pas abordée (j’en ai une petite idée, mais je vais devoir (avec plaisir) lire les travaux de Levin pour avoir une réponse validée).
Critique : Une autre question n’est pas abordée ; la théorie d’un modèle est complète le théorème d’incomplétude de Gödel ne s’applique pas à cette théorie car elle n’en vérifie pas toutes les hypothèses, mais pourquoi un processus probabiliste donne-t-il les mêmes résultats, ou plutôt comment faut-il interpréter ce résultat ? Est-ce que cela veut dire que la probabilité qu’un processus probabiliste donne une théorie complète est nulle (de la même façon que la probabilité de tirer un nombre réel au hasard qui ne soit pas transcendant est nul, alors que nous en connaissons tous beaucoup) ?
Deuxième lien : Les énoncés indécidables sont la règle et non l’exception ; en écrivant au hasard un énoncé, la probabilité pour qu’il soit indécidable tend vers 1 quand la longueur de l’énoncé tend vers l’infini (l’indécidabilité serait fille de la complexité).
Critique : les explications sur la complexité sont claires, pertinentes et très intéressantes, néanmoins il y a un aspect qui me gêne : certes « le monde des vérités mathématiques est inaccessible », mais il n’est pas utile d’invoquer Gödel ou ses successeurs pour cela, par exemple avec un ensemble très « simple » (pas tant que cela) et en tout état de cause très « naturel », à savoir les entiers naturels, il n’est pas possible de définir tous ses sous-ensembles, et même plus, un tirage aléatoire (infini, donc il n’est pas question de le réaliser) a plus de chance de donner un ensemble non définissable plutôt qu’un ensemble définissable.
Troisième lien : dans un système mathématique suffisamment évolués il existe des suites aléatoires de 0 et de 1 parfaitement définissables, mais dont la valeur de chaque élément est indécidable (ce qui est pire que le nombre Ω de Chaitin).
Critique : le mot aléatoire fait ici référence à la définition de Per Martin-Löf, ce qui est expliqué dans l’article, mais du coup, j’ai l’impression que le mot hasard n’a pas tout à fait le même sens dans cette partie que dans les autres de l’article.
Critique globale : je ne suis pas en accord avec certains usages du vocabulaire, mais il s’agit sans doute d’un TOC chez moi.
Conclusion : j’ai personnellement apprécié cet article qui est au cœur de ma spécialité, et comme j’ai arrêté la recherche il y a 30 ans, je n’étais pas au courant des évolutions qui y sont décrites ; leur description, même succincte, va me permettre de faire les recherches nécessaires sur le net ; néanmoins je trouve, c’est donc un avis personnel, que le cœur du problème n’est pas abordé ; et j’avoue ne pas avoir une image nette du profil du lecteur idéal (un spécialiste du sujet qui n’est pas au fait des dernières découvertes, peut-être
Je ne saurais trop conseiller la lecture de cet article, même si, ou peut-être surtout parce que, il nécessite de l'approfondir (sans doute la vertu N°1 de la vulgarisation).
Bonne lecture
-----
Envoyé par Médiat 
Ising demandait une clarification sur une partie du texte de Médiat. Pourquoi faudrait-il ouvrir un nouveau sujet pour une telle clarification?