P vs NP – Deuxième épisode, le 8 mars 2021 – Retranscription

Pour une raison X ou Y j’ai oublié à l’époque de mettre en ligne la retranscription de cette vidéo. Je la retrouve à l’occasion de la rédaction en ce moment de mes conclusions sur la conjecture P vs NP. Ce que je disais là n’exprimait pas par avance mes conclusions à venir : il s’agissait d’une réflexion en cours mais elle me semble toujours refléter en gros des choses que je pense encore aujourd’hui.

Nous sommes le 8 mars 2021 et ce sera probablement une vidéo à diffusion restreinte parce que la dernière fois que j’ai parlé de ce genre de choses sur mon blog, il y a quelqu’un qui a dit : « Ah, vous n’y comprenez rien. C’est des propos café du commerce. Vous êtes sorti du domaine de vos compétences » … J’aurais pu simplement éliminer son message mais alors bon, le type serait resté convaincu qu’effectivement, je ne comprenais pas ce que je disais et j’ai préféré lui répondre en disant : « Non, ce qui vous fait réagir comme ça, c’est que vous ne voyez pas qu’il s’agit d’un débat classique à l’intérieur des discussions sur les fondements des mathématiques et que je me situe à un endroit bien particulier qui est l’empirisme, ce qui est appelé empirisme ou est appelé aussi le « point de vue critique » ou qui est appelé aussi l’antiréalisme par opposition à la position platonicienne ». Alors, je résume. La position platonicienne, c’est considérer que le mathématicien est un explorateur dans un monde qui existe véritablement et Bertrand Russell riait en pensant à Gödel, en pensant qu’il était de ce type-là en disant : « Son rêve, c’est que quand il mourra et qu’il rouvrira les yeux après, il verra inscrit en lettres de feu le signe de la négation logique au firmament ». Ce qui prouve que Russell, lui, était un empiriste, était un antiréaliste. Les antiréalistes, les empiristes considèrent, à la suite d’Aristote, que l’activité mathématique n’est pas une activité d’explorateur, de découvreur de continent encore inconnu, que c’est une entreprise de type invention. On se définit un langage et on invente un certain nombre de choses dans ce cadre-là.

Et si le programme de Hilbert tenait toujours ?
(Et si Gödel, Church, Turing, Kleene avaient été de mauvaise foi ?)

Ce que j’ai pu montrer dans Comment la vérité et la réalité furent inventées c’est qu’est-ce qui guide le mathématicien pour ne pas faire absolument n’importe quoi, le platonicien ? En fait, il est guidé par son intuition du monde réel, enfin de la réalité objective telle qu’il la conçoit. C’est-à-dire qu’il a des intuitions et je mettais en évidence ce que je viens de dire en m’intéressant à l’histoire du calcul infinitésimal par Leibniz et Newton essentiellement et que, comme Berkeley l’a remarqué par la suite, en fait, ils ne font pas des mathématiques, ils mettent au point un outil, un outil pour décrire la mécanique céleste – outil qui n’existe pas encore. Et ils ne font pas de la bonne mathématique : ils éliminent, comme les « fantômes de quantités disparues », des quantités en les considérant négligeables, etc. Il y a des tas de raccourcis. Pourquoi ces raccourcis ? Et là, je le souligne, c’est simplement parce qu’ils veulent coller à la réalité physique. En fait, ce qui les guide dans la mise au point de ce calcul différentiel, ce n’est pas une rigueur mathématique : ils sacrifient la rigueur mathématique, comme le dit Berkeley, quand il leur faut coller à la réalité : le mouvement des astres. Entre la physique et un purisme mathématique, ils choisissent à tout moment la physique comme étant le cadre de référence.

Ce n’est pas vrai pour tout, ce n’est pas vrai dans le même degré pour tous les objets mathématiques qui ont été inventés. Mais on le sait par l’histoire des mathématiques et l’histoire de la physique, en général, quand un nouvel objet mathématique est créé, soit il est rapidement oublié parce que, voilà, ça ne sert à rien, soit il y a des physiciens embusqués dans un coin – ça a été le cas d’Einstein par rapport aux tenseurs – dès qu’on met au point les tenseurs comme objet mathématique, il saute dessus et il l’utilise pour sa théorie de la relativité.

Donc il y a, voilà, c’est un tango : un tango entre mathématiciens et physiciens. Les mathématiciens croient souvent qu’ils sont en train simplement de découvrir un monde mais, en fait, ils sont en train de l’inventer. Je suis moi, délibérément, je dirais, de manière militante, dans le camp des aristotéliciens empiristes antiréalistes : ils sont en train de l’inventer mais ils croient qu’ils explorent, ils croient qu’ils découvrent des choses et quand ils utilisent un procédé qui est un procédé en réalité illégitime et que ce procédé illégitime, comme la diagonalisation de Cantor, fait apparaître que, quand on a donné une définition qui permet une énumération complète d’un certain type de nombres, que par un processus de diagonalisation, on va faire apparaître des nombres qui ne sont pas dans la liste qui a été établie. Et donc, Cantor, qu’est-ce qu’il fait quand il découvre ça ? Il dit : « Eh bien, voilà, il y a un certain nombre de nombres auxquels on n’avait pas pensés, qu’on n’avait pas encore découverts, les nombres transfinis ».

Bon, il y avait une autre approche possible. Quand il voit apparaître en manipulant des nombres qui sont dans sa liste complète, quand il voit apparaître d’autres nombres qui ne sont pas dans sa liste complète, la réaction d’un antiréaliste, d’un empiriste, de quelqu’un qui n’est pas platonicien, c’est de dire : « Votre définition d’une « liste complète » était inexacte, était fautive. Il faut que vous y retourniez pour qu’elle puisse inclure ces nouveaux nombres que vous avez vu apparaître », voilà.

Alors, qu’est-ce qui va se passer, qu’est-ce qui se passe ? Il se passe la chose suivante, c’est que David Hilbert, un Allemand, en 1900, établit un programme. Il réagit au fait que les mathématiciens introduisent des paradoxes. Il considère qu’on fait n’importe quoi en mathématiques et il dit : « On va éliminer, on va éliminer ou si pas éliminer, on va restreindre le champ d’exercice de l’intuition du mathématicien ». Et qu’est-ce que c’est ? Moi, je viens de dire ce que c’est, cette intuition. Cette intuition, c’est l’intuition du monde physique, des choses qui sont possibles, du mathématicien dont il n’a pas la maîtrise : qu’il ne se rend pas compte que c’est cela qui se passe dans son intuition. C’est une boîte noire à ses yeux et du coup, il ne sait pas ce qui s’y passe exactement. Et qu’est-ce qu’il y a dans cette intuition ? Il y a sa compréhension du monde physique autour de nous qui revient comme ça et qui lui donne une ligne de conduite à l’intérieur de son exploration supposée qui est en fait son invention de certaines choses.

Bon, alors, il y a un petit paradoxe dans le fait qu’Hilbert est lui un platonicien mais il va en même temps, je dirais, définir le programme des mathématiques comme le voudraient les empiristes ou les antiréalistes. Qu’est-ce qu’il va dire ? Il va dire : « Eliminons à l’intérieur des mathématiques le recours à l’intuition. Définissons un langage. Définissons les propositions qu’on peut produire de manière valide, légitime, à l’intérieur de ce langage et restons à l’intérieur de cela et s’il faut faire des considérations supplémentaires, appelons ça non pas mathématiques mais « métamathématiques » et, dit-il, il y a bien un moment où… » et là, il y a une certaine confusion chez lui dans le terme d’intuition parce qu’il renvoie à la fois à ce que nous appelons l’intuition, c’est-à-dire la boîte noire des décisions que nous prenons sans comprendre exactement comment ça marche et intuition au sens de ce qui contient la perception, la simple perception. Il dit : « Bon, il y a bien un moment en amont où il y a simplement, je dirais, au lieu de l’intuition, il y a bien de la perception ». Là, on est d’accord mais maintenons ça dans ce que nous appelons métamathématiques, voilà, et on va séparer les deux et on va faire des mathématiques dans un champ extrêmement restreint, d’un langage qu’on a défini, des propositions qui sont valides, des propositions qu’on peut dériver à l’intérieur de cela par des démonstrations dont on donne les règles précises, etc. : le programme de Hilbert.

Et alors, qu’est-ce qui va se passer ? Et en fait, il y a un parallèle, il y a un parallèle entre ce que je vais dire maintenant sur ce qui va se passer et ce qui s’est passé au 16ème siècle avec l’apparition de gens comme Kepler, comme Galilée. Ils vont faire un coup de force. Un coup de force, c’est-à-dire qu’ils vont remettre en question un certain nombre de choses qui avaient été établies par la scolastique, c’est-à-dire la distinction entre parler du réel – c’est-à-dire le monde tel qu’il est, voilà, d’une certaine manière inconnaissable puisque, comme l’avait dit Kant, nous sommes outillés pour comprendre une partie de ce monde mais nous ne sommes probablement pas outillés pour comprendre le tout – et ce qu’on appelait la « réalité objective » qui est une description dont les platoniciens du départ, les néo-platoniciens, avaient bien compris que c’était une représentation, que ce n’est pas le Réel lui-même, que la « réalité objective », c’est la partie de ce Réel que nous pouvons appréhender par nos raisonnements de type logique et par les mathématiques. Et donc, il y a un reste, il y a une différence. Si vous faites Réel [« Être-donné »], c’est-à-dire, voilà, le monde tel qu’il est, moins « réalité objective », il y a un reste, il y a un reste, il y a une partie qu’on ne peut pas comprendre. Par exemple, René Thom dira : « Nous sommes dans un monde à 4 dimensions qui apparaît non-déterministe mais le monde en réalité a davantage de dimensions que cela et donc, la partie qui manque c’est, disons, N le nombre inconnu de dimensions – 4 ». Le reste, c’est ce qui n’est pas perçu, c’est le N-4, c’est les dimensions auxquelles nous n’avons pas accès dans la perspective de René Thom.

Bon, alors Hilbert propose son programme. On va faire des mathématiques et là, à tout moment, on ne parle pas de l’intuition. On ne parle pas de « sens commun » comme le fera Turing dans son article de 1954. On ne dira pas : « Il y a des choses que la raison ne peut pas percevoir » dans la conclusion aussi de l’article de 1954 de Turing. Non, on fait des mathématiques dans le cadre : c’est un jeu, comme aux échecs. Aux échecs, on ne peut pas mettre deux pièces dans la même case, des choses de cet ordre-là : on ne peut pas décider d’enlever certaines de ses propres pièces provisoirement de l’échiquier si elles n’ont pas été prises par l’adversaire et ainsi de suite. Programme de Hilbert en 1900.

Et vont apparaître, comme les Galilée, comme les Tycho-Brahé, comme les Kepler, un certain nombre de gens qui ne vont pas respecter les règles qui existaient jusque-là. Je les appelle des jeunes turcs dans Comment la vérité et la réalité furent inventées ». On va voir apparaître en mathématiques, vis-à-vis de ce programme de Hilbert, on va voir apparaître des jeunes turcs, essentiellement Kurt Gödel, Alonzo Church, Stephen Kleene, et Alan Turing. Ce sont les gens qui vont dire qu’ils ont montré que le programme de Hilbert n’était pas faisable, réalisable. Ils vont montrer qu’il y a des incohérences. Ils vont montrer que l’arithmétique est incomplète comme c’est le cas pour Gödel mais, que vont-ils faire, que vont-ils faire pour le faire ? Ils ne vont pas respecter les règles du jeu qu’avait défini Hilbert. Il y aura un recours systématique à l’intuition. Ils introduiront, comme le fera Turing, un « oracle » qui est une boîte noire pour des problèmes qu’on ne sait pas comment résoudre mais on va faire provisoirement comme s’il y avait, voilà, une boîte noire qu’on pouvait mettre-là et ça va nous permettre de définir différents degrés d’insolvabilité de problèmes, etc.

On va utiliser les paradoxes de manière systématique. On va invoquer ces paradoxes et on va dire : « C’est la preuve de quelque chose » et c’est exactement la chose que Hilbert avait prohibée. C’était parce qu’il y avait ces paradoxes, parce qu’on avait permis ces paradoxes… Je vais dire ce que c’est, ces paradoxes. C’est parce qu’il y avait ces paradoxes qu’Hilbert a établi son programme. Or, que font les jeunes turcs Church, Kleene, Turing, Gödel ? Ils font un recours massif à ces paradoxes. Ils considèrent – moi j’ai appelé ça l’autre jour, il faut appeler ça « quitter la route ». Qu’est-ce que ça prouve ? Ça ne prouve rien du tout. J’avais dit : « Ça prouve simplement que le gars ne sait pas conduire ». Dans le cadre défini par Hilbert, ils montrent qu’ils ne savent pas conduire mais ils vont affirmer qu’ils ont remis en cause une fois pour toute le programme de Hilbert en ne le respectant pas.

Qu’est-ce qui leur permet de faire ça ? C’est parce qu’il y a un platonisme sous-jacent. Ils vont utiliser des modes de preuve qui sont de bonne qualité selon Aristote, d’autres, de très mauvaise qualité selon Aristote, des choses qu’on ne devrait jamais introduire dans une démonstration mathématique parce qu’ils ne font pas la distinction entre les différents types d’arguments et la qualité convaincante, persuasive, de conviction de ces types d’arguments. Pourquoi est-ce qu’ils ne le font pas ? Parce qu’ils sont platoniciens, c’est-à-dire que, comme ils découvrent un monde – que vous découvriez une nouvelle espèce de coccinelle dans la jungle amazonienne parce que vous étiez parti dans une expédition qui avait coûté un million à préparer pour rechercher cette coccinelle ou que vous la découvriez par hasard, en-dessous d’une feuille, ça n’a pas d’importance, vous avez trouvé cette coccinelle – et c’est ça qu’ils vont faire. Tous les procédés sont bons, tous les procédés sont bons pour prouver que le programme d’Hilbert ne peut pas être respecté. Résultat, c’est que, quand on commence à poser… comme par exemple quand Stephen Cook produit son théorème, il le fait dans un cadre où on considère déjà comme admis les résultats de Gödel, les résultats de Church, de Kleene et de Turing. C’est dans un cadre où on n’a pas respecté le cadre qu’avait défini Hilbert pour son programme mais on considère néanmoins que le programme d’Hilbert est irréalisable alors qu’on est en infraction totale avec la définition qu’il avait donnée du problème.

Alors, quand apparaît le problème « P vs NP », « P et NP », « est-ce que P est égal à NP », ça apparaît dans un cadre – on est en 1971 avec le théorème de Cook – où tous les procédés utilisés par mes jeunes turcs Church, Kleene, Turing, Gödel – je ne vais pas tout le temps répéter la même liste –  il est considéré comme admissible ce qu’ils ont fait.

Qu’est-ce ça pose ? Ça pose le problème de la validité de ce qu’ils considèrent avoir établi. Gödel, dans son second théorème, considère avoir établi l’incomplétude de l’arithmétique et là, qu’est-ce que j’ai fait dans mon livre Comment la vérité et la réalité furent inventées, j’ai pris systématiquement la démonstration de Gödel, de son théorème, et, bon, j’avais une boîte à outils dont je rappelle les éléments principaux : la critique de Perelman qui, donc, fut mon professeur de philosophie à Bruxelles, grand logicien qui avait critiqué la démonstration de Gödel en mettant en évidence que, voilà, il avait réintroduit les paradoxes que Hilbert avait voulu qu’on n’utilise pas, la critique de Georges-Théodule Guilbaud qui fût mon professeur à l’Ecole pratique des hautes études qui est, lui, mathématicien et, lui, ce qu’il reprochait essentiellement au théorème de Gödel, c’est que, justement, comme ce que j’ai dit pour la diagonalisation, on travaille avec des définitions boiteuses. On dit : « Voilà, je m’intéresse aux nombres que j’ai définis de telle manière » mais en fait, c’est une définition incomplète. On n’a pas dit véritablement tous les nombres qui seraient inclus dans ça ou bien on en donne une définition purement dynamique et ça renvoie à la discussion classique à la fin du 19ème sur l’infini. C’est quoi l’infini ? Est-ce que c’est une vraie catégorie qu’on peut manipuler ou bien est-ce qu’il n’y a jamais… On reprend la distinction entre un infini en acte et un infini en puissance. Bon, on utilise les catégories aristotéliciennes de l’en puissance et de l’en l’acte et il y a confusion entre un infini en puissance et un infini en acte, c’est-à-dire qui est en train véritablement de se réaliser. Un infini en acte n’est en réalité pas réalisable puisqu’on ne peut pas faire une énumération. Il n’y a pas de définition en extension, par la liste complète, par l’énumération complète des nombres puisque la définition même du nombre infini est que cette opération ne pourra pas être terminée, voilà, elle ne s’arrêtera jamais.

Alors, où est-ce que ça nous mène vis-à-vis du problème P et NP ? Il est bâti entièrement sur le fait que, voilà, que mes 4 jeunes turcs auraient eu raison, auraient détruit le programme de Hilbert. En fait, le programme de Hilbert, il a une faiblesse bien entendu, c’est qu’il dit : « On va quand même garder l’intuition. On ne peut pas s’en passer dans les métamathématiques » mais je crois qu’il y a moyen de restreindre, même dans les métamathématiques, même dans la description de ce qui est fait, il y a moyen de restreindre le recours à des procédés dont on ne peut pas déterminer véritablement la nature. Quelle est la plus grande faiblesse ? Bon, il y en a plusieurs et là, dans mon démontage de la démonstration de Gödel, je mets en évidence tous les procédés. Une des faiblesses, je viens de la mentionner, c’est qu’en fait, on parle d’ensembles dont les termes ne sont pas définis de manière sans ambigüité. On définit par exemple des suites qui sont en train encore de se constituer quand on en parle, dont on n’a pas encore trouvé tous les éléments et dont parfois on ne sait pas exactement comment on va encore trouver les éléments supplémentaires et alors, on a la grande surprise dans la diagonalisation qu’on trouve des nombres auxquels on n’avait pas pensé mais qui auraient dû être dans la liste du départ. Il y a confusion. L’autre grande difficulté, c’est qu’il y a confusion entre plusieurs niveaux et ça, on le savait déjà, on l’avait déjà dit quand on s’était intéressé au paradoxe de Russell sur l’ensemble qui contient tous les ensembles qui parlent d’eux-mêmes, etc., quand on fait de l’autoréférence, quand on parle de soi-même comme dans le paradoxe du crétois. Epiménide dit que les Crétois sont des menteurs. Or, Epiménide est un Crétois, donc il est un menteur lui-même, donc quel statut attribuer à ce qu’il dit sur les Crétois et à ce qu’il dit en général ?

Dans ma critique de Gödel, je mets en évidence l’autre grande difficulté. C’est une confusion entre syntaxe et sémantique. L’exemple le plus simple que je donne c’est un enfant à qui on dit : « Il faut trouver une petite pièce » et il trouve la petite pièce mais dans la même boîte où il y a la petite pièce, il y a un petit billet qui dit : « Tu n’as pas trouvé la pièce » et l’enfant montre ça à ses parents et, selon Church, Kleene, Turing, il y aurait une contradiction puisqu’il aurait trouvé la pièce et il n’aurait pas trouvé la pièce mais il y a un statut tout à fait différent dans les deux éléments qu’on a. Il y a, d’une part, le fait que l’enfant a vraiment trouvé la pièce. Il a la pièce en main. Et d’autre part, il a simplement un bout de papier où il est écrit qu’il n’a pas trouvé la pièce. C’est pas la même chose et dans le monde dans lequel nous sommes, l’élément qui doit primer, c’est le fait qu’il a trouvé la pièce. Le commentaire qui est fait sur le bout de papier est un commentaire faux. Ce n’est pas une vraie description de la situation.

Alors que fait par exemple Gödel ? Il fait un ensemble d’opérations sur des formules qu’on peut produire, qui sont des formules valides, et il produit une formule valide et il va l’interpréter, c’est-à-dire lui donner un sens. Il ne va pas l’interpréter de la manière qui est considérée comme l’interprétation de type classique en mathématiques, c’est-à-dire d’attribuer à X ou Y des nombres, des valeurs. Quand je dis A + B = C, je peux interpréter ma formule en disant A, c’est 3, B, c’est 2 et C, c’est 5 parce que ma formule qui était A + B = C, je l’interprète comme 2 + 3 = 5. Ça, c’est une interprétation mais il y a un autre type d’interprétation et là, il y a véritablement une escroquerie de Gödel, c’est qu’il va faire un codage. Il va prendre sa formule qui est une formule non-interprétée. C’est X + Y machin, etc. Il ne va pas l’interpréter en attribuant des valeurs aux variables, A, C, X, Y, il va opérer un codage. Il va prendre sa formule et il va inventer un code qui va transformer sa formule en une affirmation « je suis vraie » ou « je suis fausse ». C’est pas une interprétation au sens classique, c’est un codage, c’est un encodage. Il va s’amuser à trouver un langage qui va lui permettre de dire : « Si j’écris X, Y, Z, etc., je le code en ce que je dis-là est vrai ou c’est faux ». C’est une astuce, c’est une astuce parce que la capacité à dire qu’une formule est vraie ou elle est fausse, elle est donnée par un certain nombre de procédures et c’est un être humain jusqu’ici – ça peut être une machine aussi maintenant, une machine intelligente – qui va vérifier si la procédure a bien été appliquée, c’est-à-dire que la personne à qui on demandera de justifier que ce soit vrai ou faux pourra donner sa démonstration comment elle est arrivée là, tandis que la petite languette de papier où il est dit : « Tu ne m’as pas trouvée » ou l’encodage qui dit : « Cette proposition est fausse », elle n’a pas la capacité de dire comme elle est arrivée à cette conclusion. Ça, je crois l’avoir bien mis en évidence dans Comment la vérité et la réalité furent inventées. Ce n’est pas la même chose, ce n’est pas la même chose.

Dans l’article de 1936 de Turing sur les nombres énumérables, qu’est-ce qu’il utilisait comme procédé ? Il utilise la diagonalisation. Bon, dans le papier de 1954 qui s’adresse à un plus grand public, qu’est-ce qu’il utilise ? Il utilise la confusion entre syntaxe et sémantique. Qu’est-ce qu’il fait ? Il donne deux définitions. Le cas 1, c’est le cas où à la fin de la formule, on va trouver B. Et le cas 2, c’est le type de problème dans lequel on va trouver comme solution à la fin W. Il fait une démonstration à partir de ça. Il a défini ça comme axiome. Il va faire une démonstration et dans sa démonstration, il va montrer qu’en fait non, dans le cas 1, c’est W qu’on trouve et dans le cas 2, c’est B et il va dire : « Il y a une contradiction ». Voilà, du coup, ça ne marche pas, du coup, on ne peut pas définir une procédure qui va pouvoir dire si un problème est soluble ou s’il ne l’est pas.

Qu’est-ce qui s’est passé-là ? Sémantique et syntaxe. Quand il arrive à dire que le cas 1 débouche sur W, qui est le contraire de ce qu’il affirmait dans sa définition, c’est à la suite d’une démonstration qu’il vient de faire. D’accord, c’est dans un théorème : un théorème a prouvé que le résultat pour 1, c’est W et pour 2, c’est B. Il démontre qu’au cas 1 correspond W et qu’au cas 2 correspond B, ce qui est le contraire de ce qu’il avait mis à son point de départ. Mais son point de départ, ce n’était pas un théorème : c’était une définition qu’on appelle en mathématiques un « axiome ». Ce qui veut dire que c’était une affirmation gratuite. Elle n’est pas gratuite dans la mesure où on pourrait dire qu’il y a des conséquences qui en découlent. Mais dans sa démonstration, il n’utilise pas du tout le fait qu’il a dit que c’était B pour le cas 1 et W pour l’autre, il ne l’utilise pas : c’est un truc qui est écrit là, c’est du même niveau que la petite languette de papier dans la boîte qu’ouvre l’enfant qui dit : « En fait, tu n’as pas trouvé la pièce ». C’est du même niveau que ça. Il n’y a pas moyen de le justifier : c’est introduit dans une définition et ce n’est pas utilisé.

Bon, il faudrait que j’en sois entièrement sûr. Il faut que je refasse entièrement la démonstration mais je mettrai ma tête (avec ma main) à couper, ma tête à couper à ce stade-ci de ma réflexion qu’il ne l’utilise pas dans sa démonstration et, par conséquent, c’est absolument indifférent qu’il ait mis le bon résultat au départ. Pourquoi est-ce qu’il fait ça ? Pourquoi est-ce qu’il croit qu’il peut le faire ? Parce qu’il est platonicien, parce qu’il croit qu’il découvre un monde comme un monde où on découvre de nouvelles coccinelles. Et voilà : il ne prend pas au sérieux le programme d’Hilbert. Il ne prend pas au sérieux le fait qu’il est entièrement lié aux définitions qu’il donne et de savoir s’il est au niveau qu’Hilbert appellerait mathématique ou s’il est au niveau qu’Hilbert appellerait métamathématique. Bon, ça fait partie des choses que ces Kleene, Church, Gödel et Turing font. Ils n’utilisent plus du tout la distinction entre mathématiques et métamathématiques donc, de fait, ils ne peuvent pas réfuter le programme d’Hilbert.

Alors, quand on s’intéresse maintenant au problème P et NP, on est dans un univers où les platoniciens ont gagné pour toute la définition de départ. Donc, quand Cook commence son théorème et qu’il dit : « Je peux utiliser la notion d’oracle de Turing, etc. », les dés sont pipés. Les dés sont pipés : on est dans un monde mathématique incontrôlable, on ne sait plus si on est au niveau sémantique ou au niveau syntaxique. On utilise des procédés qui devraient simplement montrer que la définition de départ n’était pas la bonne. Si on parle de toute la suite des nombres et qu’on en trouve encore d’autres, c’est parce qu’en réalité la définition n’était pas bonne. C’est pour ça qu’on découvre des nombres qu’on avait oubliés. On les avait oubliés, il faut les remettre dans la liste, il faut refaire la liste, il faut refaire la définition pour en tenir compte, pas considérer qu’on a découvert des nouveaux continents inconnus ou des planètes inconnues ou des étoiles inconnues comme l’a fait Cantor.

Alors, qu’est-ce que ça dit de la solution au point où j’en suis ? Qu’est-ce que ça dit de la solution de P et NP ? Eh bien, ça ne dit rien du tout. Ça dit que les règles du jeu sont inutilisables. Alors je répare avec Yu Li avec qui je travaille là-dessus. On n’aura pas un million de dollars puisque le problème de résoudre P et NP, c’est selon la manière dont il a été défini jusqu’ici, c’est-à-dire après la contre-révolution. Ce n’est pas une révolution, c’est une contre-révolution. Après la contre-révolution des 4 jeunes turcs contre le programme de Hilbert, qu’est-ce qu’il faudrait faire ? Il faudrait revenir au programme de Hilbert : poser le problème, voilà : des solutions de type polynomial, poser la question de la recherche exhaustive sur un échantillon qui ne peut pas être infini parce qu’on ne peut pas faire de recherche exhaustive sur un échantillon qui est défini comme infini, etc., c’est-à-dire avoir un problème défini de manière claire sans recours à l’intuition, sans dire comme Turing : « Ah oui, eh bien, finalement, on voit bien qu’il faudra faire appel au sens commun parce que la raison ne suffit pas pour expliquer ce que je viens de dire ». T’es plus dans le programme de Hilbert mon gars si tu dis que tu sais pas exactement ce que tu es en train de faire ! et c’est ce qu’on peut voir, c’est que, et dans le texte de 1936, et dans le texte de 1954, les règles ne sont pas précises, et c’est pour ça qu’à tout moment, on peut, voilà, botter en touche, on peut envoyer le ballon en dehors du terrain et dire : « Ça prouve que le terrain était mal défini ! ». Non, non, c’est parce que toi, tu n’as pas bien shooté, c’est pour ça que tu te retrouves en-dehors. Il faut revenir à l’intérieur.

Voilà, ce n’est pas une conclusion définitive, c’est un point d’étape sur ce travail que nous avons fait ensemble Yu Li et moi, au point où nous en sommes arrivés après les efforts qui représentent 8, 9 ou 10 semaines d’effort. Ce n’est pas terminé mais je crois que j’ai balisé la manière dont il faudra dire ce que nous pourrons dire par la suite.

Voilà, allez… Je ne sais pas si je dis « À bientôt » comme quand c’est des vidéos que je montre à tout le monde. Là, je ne sais pas où on en est. Allez…

Partager :

Une réponse à “P vs NP – Deuxième épisode, le 8 mars 2021 – Retranscription”

  1. Avatar de Maddalena Gilles
    Maddalena Gilles

    Des tas de gens s’amusent à « botter-en-touche », puis à dire que le terrain était mal « défini », c’est bien vrai…

    Alors ils sortent de leur chapeau magique un « 49/3 » bien opportun pour mieux définir le…?
    Le terrain voyons !
    ;¬)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Contact

Contactez Paul Jorion

Commentaires récents

Articles récents

Catégories

Archives

Tags

Allemagne Aristote bancor BCE Boris Johnson Bourse Brexit capitalisme centrale nucléaire de Fukushima Chine Confinement Coronavirus Covid-19 dette dette publique Donald Trump Emmanuel Macron Espagne Etats-Unis Europe extinction du genre humain FMI France François Hollande Grèce intelligence artificielle interdiction des paris sur les fluctuations de prix Italie Japon John Maynard Keynes Karl Marx pandémie Portugal robotisation Royaume-Uni Russie réchauffement climatique Réfugiés spéculation Thomas Piketty Ukraine ultralibéralisme Vladimir Poutine zone euro « Le dernier qui s'en va éteint la lumière »

Meta