Illustration par DALL-E (+PJ)
La sous-discipline dite « fondements des mathématiques » permet à des mathématiciens, logiciens, informaticiens et philosophes de s’interroger quant à la nature profonde de questions susceptibles de sembler non-problématiques aux praticiens de ces quatre disciplines envisagées séparément mais qui apparaissent rapidement opaques quand leurs points de vue sont rapprochés, les présupposés de chacun de ces points de vue étant implicites et le plus souvent lacunaires, étant basés sur les intuitions culturellement partagées par de petites communautés insouciantes d’une véritable rigueur formelle.
Problèmes classiques d’« indécidabilité » :
1) Le problème de correspondance d’Emil Post (PCP) : Il est impossible de déterminer s’il existe deux séquences correspondantes de caractères L1 et L2 de même longueur pour un alphabet A donné.
2) Les propositions indécidables du second théorème d’incomplétude de Gödel : Il existe dans l’arithmétique de Principia Arithmetica, des énoncés vrais qui ne peuvent être démontrés.
3) Le problème de l’arrêt (attribué à Turing) : Il est impossible de déterminer pour un algorithme donné et une donnée d’entrée si le programme s’arrêtera de tourner ou tournera indéfiniment.
À mon sens, les ennuis démarrent aussitôt que l’on est prêt à accepter que ces trois énoncés pourraient être regroupés sous une seule rubrique, intitulée « indécidabilité ».
La conjecture P vs NP soulève la question suivante : « Quelle est la complexité de la solution d’un problème particulier ET existe-t-il une application (au sens mathématique du terme) entre la structure de l’algorithme permettant de vérifier que le problème a été résolu et celle de l’algorithme utilisé pour résoudre initialement le problème ? ». P vs NP s’efforce de mettre à jour des régularités dans l’éventail couvrant l’ensemble des « problèmes solubles ».
Il existe maintenant une deuxième catégorie : celle des « problèmes insolubles ». Comme cela s’applique à mon sens aux trois problèmes mentionnés ci-dessus, cette catégorie pourrait regrouper des problèmes d’une multiplicité de natures différentes, si bien que le terme « indécidabilité » pourrait constituer en les mettant sous une seule rubrique, une source de confusion plutôt qu’un moyen d’offrir un éclairage.
En effet,
1) Le problème de correspondance d’Emil Post constitue une énigme au sens classique ;
2) Les « propositions indécidables » du second théorème d’incomplétude de Gödel sont en réalité des paradoxes rebaptisés ainsi ;
3) Le problème de l’arrêt (attribué à Turing) est celui de la prévisibilité du résultat d’une expérience.
Je défends la thèse selon laquelle lorsque l’on dit qu’« Il existe dans l’arithmétique de Principia Arithmetica, des énoncés vrais qui ne peuvent être démontrés », le terme « vrai » est en réalité indéfini, autorisant une référence implicite à des faits empiriques, permettant à ceux-ci de se glisser dans la démonstration comme passagers clandestins, en tant que type de « vérité » communément admise mais non formellement définie.
Laisser un commentaire