![\"\"](\"https:\/\/www.pauljorion.com\/blog\/wp-content\/uploads\/DALL\u00b7E-2023-04-22-20.02.41-Pythagoras-explains-a-set-of-equations-to-a-group-of-surfers-in-the-style-of-a-photo-1.png\")
<\/p>\n<\/p>\n
Illustration par DALL-E (+PJ)<\/em><\/p>\n La sous-discipline dite \u00ab\u00a0fondements des math\u00e9matiques\u00a0\u00bb permet \u00e0 des math\u00e9maticiens, logiciens, informaticiens et philosophes de s’interroger quant \u00e0 la nature profonde de questions susceptibles de sembler non-probl\u00e9matiques aux praticiens de ces quatre disciplines envisag\u00e9es s\u00e9par\u00e9ment mais qui apparaissent rapidement opaques quand leurs points de vue sont rapproch\u00e9s, les pr\u00e9suppos\u00e9s de chacun de ces points de vue \u00e9tant implicites et le plus souvent lacunaires, \u00e9tant bas\u00e9s sur les intuitions culturellement partag\u00e9es par de petites communaut\u00e9s insouciantes d’une v\u00e9ritable rigueur formelle.<\/p><\/blockquote>\n Probl\u00e8mes classiques d’\u00ab ind\u00e9cidabilit\u00e9\u00a0\u00bb :<\/p>\n 1) Le probl\u00e8me de correspondance d’Emil Post<\/em> (PCP) : Il est impossible de d\u00e9terminer s’il existe deux s\u00e9quences correspondantes de caract\u00e8res L1 et L2 de m\u00eame longueur pour un alphabet A donn\u00e9.<\/p>\n 2) Les propositions ind\u00e9cidables du second th\u00e9or\u00e8me d’incompl\u00e9tude de G\u00f6del<\/em> : Il existe dans l’arithm\u00e9tique de Principia Arithmetica,<\/em> des \u00e9nonc\u00e9s vrais qui ne peuvent \u00eatre d\u00e9montr\u00e9s.<\/p>\n 3) Le probl\u00e8me de l’arr\u00eat<\/em> (attribu\u00e9 \u00e0 Turing) : Il est impossible de d\u00e9terminer pour un algorithme donn\u00e9 et une donn\u00e9e d’entr\u00e9e si le programme s’arr\u00eatera de tourner ou tournera ind\u00e9finiment.<\/p>\n \u00c0 mon sens, les ennuis d\u00e9marrent aussit\u00f4t que l’on est pr\u00eat \u00e0 accepter que ces trois \u00e9nonc\u00e9s pourraient \u00eatre regroup\u00e9s sous une seule rubrique, intitul\u00e9e \u00ab\u00a0ind\u00e9cidabilit\u00e9\u00a0\u00bb.<\/p>\n La conjecture P vs NP<\/em> soul\u00e8ve la question suivante : \u00ab\u00a0Quelle est la complexit\u00e9 de la solution d’un probl\u00e8me particulier ET existe-t-il une application (au sens math\u00e9matique du terme) entre la structure de l’algorithme permettant de v\u00e9rifier que le probl\u00e8me a \u00e9t\u00e9 r\u00e9solu et celle de l’algorithme utilis\u00e9 pour r\u00e9soudre initialement le probl\u00e8me ?\u00a0\u00bb. P vs NP<\/em> s’efforce de mettre \u00e0 jour des r\u00e9gularit\u00e9s dans l’\u00e9ventail couvrant l’ensemble des \u00ab\u00a0probl\u00e8mes solubles\u00a0\u00bb.<\/p>\n Il existe maintenant une deuxi\u00e8me cat\u00e9gorie : celle des \u00ab\u00a0probl\u00e8mes insolubles\u00a0\u00bb. Comme cela s’applique \u00e0 mon sens aux trois probl\u00e8mes mentionn\u00e9s ci-dessus, cette cat\u00e9gorie pourrait regrouper des probl\u00e8mes d’une multiplicit\u00e9 de natures diff\u00e9rentes, si bien que le terme \u00ab\u00a0ind\u00e9cidabilit\u00e9\u00a0\u00bb pourrait constituer en les mettant sous une seule rubrique, une source de confusion plut\u00f4t qu’un moyen d’offrir un \u00e9clairage.<\/p>\n En effet,<\/p>\n 1) Le probl\u00e8me de correspondance d’Emil Post <\/em>constitue une \u00e9nigme au sens classique ;<\/p>\n 2) Les \u00ab\u00a0propositions ind\u00e9cidables\u00a0\u00bb du second th\u00e9or\u00e8me d’incompl\u00e9tude de G\u00f6del <\/em> sont en r\u00e9alit\u00e9 des paradoxes rebaptis\u00e9s ainsi ;<\/p>\n 3) Le probl\u00e8me de l’arr\u00eat<\/em> (attribu\u00e9 \u00e0 Turing) est celui de la pr\u00e9visibilit\u00e9 du r\u00e9sultat d’une exp\u00e9rience.<\/p>\n Je d\u00e9fends la th\u00e8se<\/a> selon laquelle lorsque l’on dit qu’\u00ab Il existe dans l’arithm\u00e9tique de Principia Arithmetica,<\/em> des \u00e9nonc\u00e9s vrais qui ne peuvent \u00eatre d\u00e9montr\u00e9s\u00a0\u00bb, le terme \u00ab\u00a0vrai\u00a0\u00bb est en r\u00e9alit\u00e9 ind\u00e9fini, autorisant une r\u00e9f\u00e9rence implicite \u00e0 des faits empiriques, permettant \u00e0 ceux-ci de se glisser dans la d\u00e9monstration comme passagers clandestins<\/a>, en tant que type de \u00ab\u00a0v\u00e9rit\u00e9\u00a0\u00bb commun\u00e9ment admise mais non formellement d\u00e9finie.<\/p>\n","protected":false},"excerpt":{"rendered":" Illustration par DALL-E (+PJ)<\/em><\/p>\n La sous-discipline dite \u00ab\u00a0fondements des math\u00e9matiques\u00a0\u00bb permet \u00e0 des math\u00e9maticiens, logiciens, informaticiens et philosophes de s’interroger quant \u00e0 la nature profonde de questions susceptibles de sembler non-probl\u00e9matiques aux praticiens de ces quatre disciplines envisag\u00e9es s\u00e9par\u00e9ment mais qui apparaissent rapidement opaques quand leurs […]<\/p>\n<\/blockquote>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8601,5470,4965,16],"tags":[7938,9182,8004,9183,9185,5335,7936,9184],"class_list":["post-135873","post","type-post","status-publish","format-standard","hentry","category-fondement-des-mathematiques","category-informatique","category-logique","category-mathematiques","tag-alan-turing","tag-emil-post","tag-fondements-des-mathematiques","tag-halting-problem","tag-indecidabilite","tag-kurt-godel","tag-p-vs-np","tag-probleme-de-larret"],"_links":{"self":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/135873","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/comments?post=135873"}],"version-history":[{"count":6,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/135873\/revisions"}],"predecessor-version":[{"id":135885,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/135873\/revisions\/135885"}],"wp:attachment":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/media?parent=135873"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/categories?post=135873"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/tags?post=135873"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}<\/p>\n\n