Français
Cet article porte sur la discussion par Gödel de la thèse de Turing. Pour l'essentiel, nous présentons des notes inédites conservées dans les Archives Gödel, qui apportent des éléments nouveaux sur la relation ambiguë de Gödel à Turing. La première section examine la position qu'avait Gödel avant 1937 sur la possibilité d'une définition de la calculabilité. La deuxième concerne directement l'interprétation par Gödel de la thèse de Turing. Dans plusieurs passages, antérieurs à 1937, Gödel qualifie de « mécaniques » les procédures définies par des règles qui font abstraction du sens des symboles et ne portent que sur leur forme extérieure. Plusieurs notes montrent ensuite que Gödel identifie la thèse de Turing comme posant que ces procédures « mécaniques » (au sens où Gödel l'entendait avant Turing) sont représentables par une machine de Turing. Ce n'est pas en toute rigueur la thèse de Turing, puisque l'article de 1937, pris à la lettre, entend définir les procédures « finies ». Ce déplacement laisse Gödel libre de critiquer, après 1964, le texte de Turing, et la définition des procédures « finies » par des machines de Turing. La dernière section est consacrée à l'analyse d'un argument élaboré contre Turing par lequel Gödel entend justifier la possibilité de procédures finies mais non mécaniques.
Turing, Gödel, machines, calculabilité, incomplétude