Blog de Paul Jorion

Si vous suivez les activités de mon blog vous n’ignorez pas que Yu Li et moi collaborons depuis quelques années sur des questions liées aux fondements des mathématiques. Yu Li est professeur d’informatique à l’Université de Picardie, elle a mis sur pied une table-ronde qui se déroulera à Rome en août 2024 dans le cadre du XXV^e Congrès Mondial de Philosophie : « Un réexamen du théorème d’incomplétude de Gödel ».

Les organisateurs de cette table-ronde expliquent dans un prospectus leur intérêt pour cette question. Voici l’entrée de Yu LI :

Présentation professionnelle :

1994-aujourd’hui : Professeur associé, Université de Picardie Jules Verne
1990-1993 : Doctorat en informatique, Université de Technologie de Compiègne
1981-1988 : M.S., B.S. en informatique, Huazhong University of Science and Technology, Wuhan, Chine

Parcours personnel de recherche :

En 1993, j’ai terminé mon doctorat en informatique à l’Université de Technologie de Compiègne, et j’ai commencé à enseigner et à faire de la recherche à l’Université de Picardie Jules Verne. D’une part, le système éducatif des universités françaises m’a beaucoup apporté en mettant l’accent sur la coopération et l’individualité ; d’autre part, l’accent mis sur le mode d’enseignement procédural m’a mise extrêmement mal à l’aise et, conjugué à la barrière de la langue, je n’ai pu m’empêcher de rencontrer de nombreuses difficultés, ce qui m’a toutefois ouvert la voie vers une nouvelle compréhension des cultures chinoise et occidentale, et en fait, de moi-même.

J’ai commencé à m’intéresser au théorème d’incomplétude de Gödel en étudiant le problème P vs NP.

Mon travail sur le problème P vs NP a commencé par l’expérience « étrange » de l’étude et de l’enseignement de la « Théorie de la complexité informatique » car peu de temps après chaque conférence sur ce sujet, j’ai, moi en premier lieu, oublié presque tout ce que j’avais enseigné, et il ne me restait que quelques définitions formelles : P, NP, NP-complétude, etc.

Dans mes recherches, la « solution pratique des problèmes NP-difficiles » me laissait perplexe, et bien que j’aie pratiqué différents algorithmes heuristiques, je me sentais séparée de la « théorie de la complexité computationnelle », et il y avait un sérieux décalage entre la théorie et la pratique.

L’intuition m’a conduit à explorer des domaines plus ouverts, tout d’abord en travaillant avec le philosophe chinois M. Jianming Zhou pour déchiffrer le théorème de Cook. Nous avons découvert qu’il y avait au niveau cognitif une confusion dans la définition de NP provenant du théorème de Cook dans son article de 1976, où Cook avait introduit l’« Oracle » dans sa démonstration, conduisant à une confusion entre le déterminisme et le non-déterminisme. Nous n’avons pas pu obtenir de réponse de nos pairs pour ce travail, et même ma participation aux discussions liées au FOM a été rejetée.

D’autre part, près de 10 ans de recherche sur le problème P vs NP nous ont amenés à un goulot d’étranglement, bien que nous ayons déchiffré la confusion au niveau cognitif qui existe dans le théorème de Cook, et que l’essence du problème NP est le problème indécidable, mais quelle est exactement l’essence du problème indécidable ? Nous n’étions pas en mesure de fournir une explication plus détaillée.

C’est alors que j’ai rencontré Paul Jorion qui m’a dit que ses recherches antérieures semblaient être liées au problème P vs NP, par exemple il avait déchiffré le théorème d’incomplétude de Gödel, et j’ai donc commencé à m’intéresser au théorème d’incomplétude de Gödel. Lorsque j’ai lu l’article de Gödel de 1931, j’ai été très perplexe et choquée de voir la proposition qui se dit elle-même indémontrable dans la preuve de Gödel, ce qui m’a rappelé l’Oracle sous la forme d’un spectre dans la démonstration de Cook.

Paul Jorion et moi-même avons assisté à Unilog2022 pour y présenter le fruit de notre collaboration.