Revue d’Histoire des Mathématiques. N° 14. Vol. 1. p. 77-111. Gödel et la thèse de Turing.

English Title : Gödel and Turing's thesis.

Résumé

Cet article porte sur la discussion par Gödel de la thèse de Turing. Pour l’essentiel, sont présentées 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.

Abstract

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.MVLcalculabilité

Notes

Fondée en 1995, la Revue d’histoire des mathématiques publie des articles originaux (en français ou en anglais) consacrés à l’histoire des mathématiques, de l’Antiquité à nos jours. (En ligne ISSN 1777-568X)
Le texte intégral des articles récents est réservé aux abonnés sur le site de la revue.

Une version texte intégral est en téléchargement sur le site SMF – Revue d’Histoire des Mathématiques

Données de publication

Éditeur Société Mathématique de France (SMF) Paris , 2008 Format 15,5 cm x 24 cm, p. 53-75
ISSN 1262-022X

Public visé chercheur, enseignant, formateur Niveau licence, master Âge 19, 20, 21

Type article de périodique ou revue Langue français Support papier

Classification