Gödel et la thèse de Turing
Revue d'histoire des mathématiques, Tome 14 (2008) no. 1, pp. 77-111.

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.

Classification : 03D10, 03F30
Mot clés : Turing, Gödel, machines, calculabilité, incomplétude
Keywords: Turing, Gödel, machines, computability, incompleteness 
@article{RHM_2008__14_1_77_0,
     author = {Cassou-Nogu\`es, Pierre},
     title = {G\"odel et la th\`ese de {Turing}},
     journal = {Revue d'histoire des math\'ematiques},
     pages = {77--111},
     publisher = {Soci\'et\'e math\'ematique de France},
     volume = {14},
     number = {1},
     year = {2008},
     mrnumber = {2493383},
     zbl = {1162.03001},
     language = {fr},
     url = {http://www.numdam.org/item/RHM_2008__14_1_77_0/}
}
TY  - JOUR
AU  - Cassou-Noguès, Pierre
TI  - Gödel et la thèse de Turing
JO  - Revue d'histoire des mathématiques
PY  - 2008
SP  - 77
EP  - 111
VL  - 14
IS  - 1
PB  - Société mathématique de France
UR  - http://www.numdam.org/item/RHM_2008__14_1_77_0/
LA  - fr
ID  - RHM_2008__14_1_77_0
ER  - 
%0 Journal Article
%A Cassou-Noguès, Pierre
%T Gödel et la thèse de Turing
%J Revue d'histoire des mathématiques
%D 2008
%P 77-111
%V 14
%N 1
%I Société mathématique de France
%U http://www.numdam.org/item/RHM_2008__14_1_77_0/
%G fr
%F RHM_2008__14_1_77_0
Cassou-Noguès, Pierre. Gödel et la thèse de Turing. Revue d'histoire des mathématiques, Tome 14 (2008) no. 1, pp. 77-111. http://www.numdam.org/item/RHM_2008__14_1_77_0/

[Ackermann 1928] Ackermann (Wilhelm) - Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann., 99(1) (1928), p. 118-133. | JFM

[Atten 2006] Atten (Mark (Van)) - Two draft letters from Gödel on self-knowledge of reason, Philos. Math., 14(2) (2006), p. 255-261. | Zbl

[Cassou-Noguès 2002] Cassou-Noguès (Pierre) - Deux figures de l'automate spirituel : Leibniz et Turing, dans Fédi (Laurent), éd., La migration des concepts, Paris : L'Harmattan, 2002, p. 51-68.

[Cassou-Noguès 2005] Cassou-Noguès (Pierre) - Gödel and ‘the objective existence' of mathematical objects, Hist. Philos. Logic, 26(3) (2005), p. 211-228. | Zbl

[Cassou-Noguès 2007] Cassou-Noguès (Pierre) - Les démons de Gödel, Paris : Seuil, 2007.

[Dawson 1997] Dawson (John W. Jr) - Logical Dilemmas : The Life and Work of Kurt Gödel, Wellesley, MA : A K Peters Ltd., 1997. | Zbl

[Dawson 2003] Dawson (John W. Jr) - Introductory note to the Gödel-Church correspondence, 2003 ; in [Gödel 1986-2003a, t. IV, p. 361-366].

[Davis 1965] Davis (Martin) - The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Ed. by Martin Davis, Hewlett, N.Y. : Raven Press, 1965. | Zbl

[Davis 1982] Davis (Martin) - Why Gödel didn't have Church's thesis, Inform. and Control, 54(1-2) (1982), p. 3-24. | Zbl

[Feferman 1991] Feferman (Solomon) - Reflecting on incompleteness, J. Symbolic Logic, 56(1) (1991), p. 1-49. | Zbl

[Gandy 1980] Gandy (Rudy) - Church's Thesis and principles for mechanism, dans Barwise & others, éd., The Kleene Symposium, Amsterdam : North-Holland, 1980. | Zbl

[Gödel 1986-2003a] Gödel (Kurt) - Collected Works, ed. by Solomon Feferman, John W. Dawson et al., Oxford : Oxford University Press, 1986-2003. | Zbl

[Gödel 1986-2003b] Gödel (Kurt) - Archives Gödel de l'Institute for Advanced Studies, conservées à la bibiothèque de l'université de Princeton (cote 0282), 1986-2003.

[Gödel 1931] Gödel (Kurt) - Über formal unentscheidbare Sätze der Principia mathematica und verwandter Systeme I, 1931 ; in [Gödel 1986-2003a, t. I, p. 144-195]. | Zbl

[Gödel 1933] Gödel (Kurt) - The present situation in the foundations of mathematics, Philos. Math., 16(1) (1933), p. 100-112 ; in [Gödel 1986-2003a, t. III, p. 45-53].

[Gödel 1934] Gödel (Kurt) - On undecidable propositions of formal mathematical systems, 1934 ; in [Gödel 1986-2003a, t. I, p. 346-372].

[Gödel 1936] Gödel (Kurt) - Über die Länge von Beweisen, Philos. Math., 16(1) (1936), p. 100-112 ; in [Gödel 1986-2003a, t. I, p. 396-398].

[Gödel 193 ?] Gödel (Kurt) - Undecidable Diophantine propositions, 193 ? ; in [Gödel 1986-2003a, t. III, p. 164-175].

[Gödel 1941] Gödel (Kurt) - In what sense is intuitionistic logic constructive ?, Philos. Math., 16(1) (1941), p. 100-112 ; in [Gödel 1986-2003a, t. III, p. 189-201].

[Gödel 1946] Gödel (Kurt) - Remarks before the Princeton bicentennial conference on problems in mathematics, 1946 ; in [Gödel 1986-2003a, t. II, p. 149-152].

[Gödel 1951] Gödel (Kurt) - Some basic theorems on the foundations of mathematics and their philosophical implications, Philos. Math., 16(1) (1951), p. 100-112 ; in [Gödel 1986-2003a, t. III, p. 304-323].

[Gödel 1958] Gödel (Kurt) - Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes, Dialectica, 12 (1958), p. 280-287 ; in [Gödel 1986-2003a, t. II, p. 240-252]. | Zbl

[Gödel 1961/ ?] Gödel (Kurt) - The modern development of the foundations of mathematics in the light of philosophy, Philos. Math., 16(1) (1961/ ?), p. 100-112 ; in [Gödel 1986-2003a, t. III, p. 374-387].

[Gödel 1964] Gödel (Kurt) - What is Cantor's Continuum Problem ?, 1964 ; in [Gödel 1986-2003a, t. II, p. 254-270].

[Gödel 1972a] Gödel (Kurt) - On an extension of finitary mathematic which has not yet been used, 1972 ; in [Gödel 1986-2003a, t. II, p. 271-280].

[Gödel 1972b] Gödel (Kurt) - Some remarks on the undecidability results, 1972 ; in [Gödel 1986-2003a, t. II, p. 305-306].

[Herbrand 1931] Herbrand (Jacques) - Sur la non-contradiction de l'arithmétique, Journal für die reine und angewandte Mathematik, 166 (1931), p. 1-8. | JFM | Zbl

[Hilbert 1926] Hilbert (David) - Über das Unendliche, Math. Ann., 95(1) (1926), p. 161-190. | JFM

[Kleene 1936] Kleene (Stephen) - General recursive functions of natural numbers, Math. Ann., 112(1) (1936), p. 727-742. | Zbl

[Kleene 1981] Kleene (Stephen) - Origins of recursive function theory, Ann. Hist. Comput., 3(1) (1981), p. 52-67. | Zbl

[Kleene 1987] Kleene (Stephen) - Gödel's impression on students in logic in the 1930s, dans Weingartner (Paul) & Schmetterer (Leopold), éd., Gödel Remembered, History of Logic, 4, Gödel Symposium, Salzburg, July 10-12, 1983, Naples : Bibliopolis, 1987, p. 49-64.

[Kleene 1988] Kleene (Stephen) - Turing's analysis of computability, and major applications of it, dans Herken (Rolf), éd., The Universal Turing Machine : A Half-Century Survey, New York : The Clarendon Press, Oxford University Press, 1988, p. 17-54. | Zbl

[Leibniz 1969] Leibniz (Gottfried W.) - Essais de théodicée (1710), éd. de Jacques Brunschvicg, Paris : Garnier-Flammarion, 1969.

[Leibniz 1966] Leibniz (Gottfried W.) - Nouveaux essais sur l'entendement humain (1765), éd. de Jacques Brunschvicg, Paris : Garnier-Flammarion, 1966.

[Mancosu 1999] Mancosu (Paolo) - Between Vienna and Berlin : the immediate reception of Gödel's incompleteness theorems, Hist. Philos. Logic, 20(1) (1999), p. 33-45. | Zbl

[Sieg 1994] Sieg (Wilfried) - Mechanical procedures and mathematical experience, dans George (A.), éd., Mathematics and mind, Logic Comput. Philos., Oxford : Oxford Univ. Press, 1994, p. 71-117. | Zbl

[Sieg 1997] Sieg (Wilfried) - Step by recursive step : Church's analysis of effective calculability, Bull. Symbolic Logic, 3(2) (1997), p. 154-180. | Zbl

[Sieg 2005] Sieg (Wilfried) - Only two letters : the correspondence between Herbrand and Gödel, Bull. Symbolic Logic, 11(2) (2005), p. 172-184. | Zbl

[Sieg 2006] Sieg (Wilfried) - Gödel on computability, Philos. Math., 14(2) (2006), p. 189-207. | Zbl

[Sinaceur 2000] Sinaceur (Hourya) - Address at the Princeton University Bicentennial Conference on Problems in Mathematics, by Alfred Tarski, Bull. Symbolic Logic, 6 (2000), p. 1-44. | Zbl

[Turing 1937] Turing (Alan) - On computable numbers, with an application to the Entscheidungsproblem, 1937 ; in [Davis 1965, p. 115-153]. | JFM | Zbl

[Turing 1939] Turing (Alan) - Systems of logic based on ordinals, 1939 ; in [Davis 1965, p. 154-222]. | JFM | Zbl

[Wang 1974] Wang (Hao) - From Mathematics to Philosophy, Londres : Routledge & Paul, 1974. | Zbl

[Webb 1980] Webb (Judd C.) - Mechanism, Mentalism and Metamathematics, Dordrecht : Reidel, 1980. | Zbl

[Webb 1990] Webb (Judd C.) - Introductory note to [Gödel 1972b], remarks 3, 1990 ; in [Gödel 1986-2003a, t. II, p. 292-304].