Gödel and Turing’s thesis

Pierre Cassou-Noguès

Revue d'histoire des mathématiques (2008)

  • Volume: 14, Issue: 1, page 77-111
  • ISSN: 1262-022X

Abstract

top
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.

How to cite

top

Cassou-Noguès, Pierre. "Gödel et la thèse de Turing." Revue d'histoire des mathématiques 14.1 (2008): 77-111. <http://eudml.org/doc/274984>.

@article{Cassou2008,
abstract = {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.},
author = {Cassou-Noguès, Pierre},
journal = {Revue d'histoire des mathématiques},
keywords = {Turing; Gödel; machines; computability; incompleteness},
language = {fre},
number = {1},
pages = {77-111},
publisher = {Société mathématique de France},
title = {Gödel et la thèse de Turing},
url = {http://eudml.org/doc/274984},
volume = {14},
year = {2008},
}

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
PB - Société mathématique de France
VL - 14
IS - 1
SP - 77
EP - 111
AB - 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.
LA - fre
KW - Turing; Gödel; machines; computability; incompleteness
UR - http://eudml.org/doc/274984
ER -

References

top
  1. [Ackermann 1928] Ackermann ( Wilhelm) – Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann., 99(1) (1928), p. 118–133. Zbl54.0056.06JFM54.0056.06
  2. [Atten 2006] Atten ( Mark (van)) – Two draft letters from Gödel on self-knowledge of reason, Philos. Math., 14(2) (2006), p. 255–261. Zbl1113.03004
  3. [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. 
  4. [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. Zbl1073.03001
  5. [Cassou-Noguès 2007] Cassou-Noguès ( Pierre) – Les démons de Gödel, Paris : Seuil, 2007. 
  6. [Dawson 1997] Dawson ( John W. Jr) – Logical Dilemmas : The Life and Work of Kurt Gödel, Wellesley, MA : A K Peters Ltd., 1997. Zbl1078.03005
  7. [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]. 
  8. [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. Zbl1099.03002
  9. [Davis 1982] Davis ( Martin) – Why Gödel didn’t have Church’s thesis, Inform. and Control, 54(1-2) (1982), p. 3–24. Zbl0519.03033
  10. [Feferman 1991] Feferman ( Solomon) – Reflecting on incompleteness, J. Symbolic Logic, 56(1) (1991), p. 1–49. Zbl0746.03046
  11. [Gandy 1980] Gandy ( Rudy) – Church’s Thesis and principles for mechanism, dans Barwise & others, éd., The Kleene Symposium, Amsterdam : North-Holland, 1980. Zbl0465.03022
  12. [Gödel 1986–2003a] Gödel ( Kurt) – Collected Works, ed. by Solomon Feferman, John W. Dawson et al., Oxford : Oxford University Press, 1986–2003. Zbl1026.01020
  13. [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. 
  14. [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]. Zbl0002.00101
  15. [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]. 
  16. [Gödel 1934] Gödel ( Kurt) – On undecidable propositions of formal mathematical systems, 1934 ; in [Gödel 1986–2003a, t. I, p. 346–372]. 
  17. [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]. 
  18. [Gödel 193 ?] Gödel ( Kurt) – Undecidable Diophantine propositions, 193 ? ; in [Gödel 1986–2003a, t. III, p. 164–175]. 
  19. [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]. 
  20. [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]. 
  21. [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]. 
  22. [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]. Zbl0090.01003
  23. [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]. 
  24. [Gödel 1964] Gödel ( Kurt) – What is Cantor’s Continuum Problem ?, 1964 ; in [Gödel 1986–2003a, t. II, p. 254–270]. 
  25. [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]. 
  26. [Gödel 1972b] Gödel ( Kurt) – Some remarks on the undecidability results, 1972 ; in [Gödel 1986–2003a, t. II, p. 305–306]. 
  27. [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. Zbl0003.04902JFM57.0056.04
  28. [Hilbert 1926] Hilbert ( David) – Über das Unendliche, Math. Ann., 95(1) (1926), p. 161–190. JFM51.0044.02
  29. [Kleene 1936] Kleene ( Stephen) – General recursive functions of natural numbers, Math. Ann., 112(1) (1936), p. 727–742. Zbl0014.19402
  30. [Kleene 1981] Kleene ( Stephen) – Origins of recursive function theory, Ann. Hist. Comput., 3(1) (1981), p. 52–67. Zbl0998.03501
  31. [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. 
  32. [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. Zbl0655.03027
  33. [Leibniz 1969] Leibniz ( Gottfried W.) – Essais de théodicée (1710), éd. de Jacques Brunschvicg, Paris : Garnier-Flammarion, 1969. 
  34. [Leibniz 1966] Leibniz ( Gottfried W.) – Nouveaux essais sur l’entendement humain (1765), éd. de Jacques Brunschvicg, Paris : Garnier-Flammarion, 1966. 
  35. [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. Zbl1051.01504
  36. [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. Zbl0816.03001
  37. [Sieg 1997] Sieg ( Wilfried) – Step by recursive step : Church’s analysis of effective calculability, Bull. Symbolic Logic, 3(2) (1997), p. 154–180. Zbl0884.03001
  38. [Sieg 2005] Sieg ( Wilfried) – Only two letters : the correspondence between Herbrand and Gödel, Bull. Symbolic Logic, 11(2) (2005), p. 172–184. Zbl1089.03005
  39. [Sieg 2006] Sieg ( Wilfried) – Gödel on computability, Philos. Math., 14(2) (2006), p. 189–207. Zbl1111.03003
  40. [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. Zbl0959.01001
  41. [Turing 1937] Turing ( Alan) – On computable numbers, with an application to the Entscheidungsproblem, 1937 ; in [Davis 1965, p. 115–153]. Zbl0016.09701JFM62.1059.03
  42. [Turing 1939] Turing ( Alan) – Systems of logic based on ordinals, 1939 ; in [Davis 1965, p. 154–222]. Zbl0021.09704JFM65.1102.02
  43. [Wang 1974] Wang ( Hao) – From Mathematics to Philosophy, Londres : Routledge & Paul, 1974. Zbl0554.03002
  44. [Webb 1980] Webb ( Judd C.) – Mechanism, Mentalism and Metamathematics, Dordrecht : Reidel, 1980. Zbl0454.03001
  45. [Webb 1990] Webb ( Judd C.) – Introductory note to [Gödel 1972b], remarks 3, 1990 ; in [Gödel 1986–2003a, t. II, p. 292–304]. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.