SMF

Gödel et la thèse de Turing

Gödel and Turing's thesis

Pierre Cassou-Noguès
Gödel et la thèse de Turing
  • Année : 2008
  • Fascicule : 1
  • Tome : 14
  • Format : Électronique
  • Langue de l'ouvrage :
    Français
  • Class. Math. : 03D10, 03F30
  • Pages : 77-111
  • DOI : 10.24033/rhm.142
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.
This paper concerns Gödel's remarks on Turing's thesis. Of fundamental importance to this analysis are unpublished notes kept among Gödel's papers. The first section concerns Gödel's position on the possibility of a definition of computability before 1937. The second and main section presents different notes on Turing's famous paper of 1937. Before 1937, Gödel qualified as « mechanical » procedures defined by rules that ignore the meaning of symbols and only consider their exterior form. Several notes then show that Gödel interpreted Turing's thesis as the claim that mechanical procedures in that sense can be represented by Turing machines. But Turing himself intended to define « finite » procedures. This shift enabled Gödel after 1964 to criticize Turing's paper. The third and last section deals with Gödel's argument against Turing, in which Gödel aimed to establish the existence of finite but non-mechanical procedures.
Turing, Gödel, machines, calculabilité, incomplétude
Turing, Gödel, machines, computability, incompleteness


Des problèmes avec le téléchargement?Des problèmes avec le téléchargement?
Informez-nous de tout problème que vous avez...