Typed letter signed 'Kurt Gödel' to Martin Davis, with manuscript annotations by both Gödel and Davis, on Gödel's contributions to Davis' book The Undecidable, and in particular Gödel's opinions on the 'Church-Turing thesis'

GÖDEL, Kurt

Edité par The Institute for Advanced Study, Princeton, New Jersey, 1965

A propos de cet article

GÖDEL SETS OUT HIS OPINION OF THE CHURCH-TURING THESIS. A highly important letter from Gödel to the logician Martin Davis in which Gödel clarifies his position on 'Church's thesis' (later called the Church-Turing thesis), which proposed an answer to the question of what constitutes 'effective calculability'. From February to May 1934, Gödel lectured at the Institute for Advanced Study on his epoch-making undecidability results of three years earlier. Mimeographed lecture notes were circulated at the time, but the lectures were not formally published until 1965, in the book The Undecidable, edited by Davis. As Gödel later wrote, "A number of misprints and oversights in the original mimeographed lecture notes were corrected when they were reprinted in [The Undecidable]. I am indebted to Professor Martin Davis for calling my attention to some of them" (Kurt Gödel CollectedWorks I, p. 371). The present letter sets out Gödel's corrections and emendations to the original lectures, for Davis to incorporate in the published version. In the lectures, Gödel noted that primitive recursive functions "have the important property that, for each given set of values of the arguments, the value of the function can be computed by a finite procedure." To this remark Gödel added a footnote that suggested that a converse of this statement could serve as a "heuristic principle". When Davis submitted to Gödel a preliminary version of his introduction to Gödel's lectures, he suggested that this footnote, together with his proposed definition of general recursive function in the same lectures, amounted to a precise characterization of the mechanically calculable functions and hence to a statement of Church's thesis. However, "Gödel in 1934 did not subscribe to Church's thesis, which as formulated in terms of lambda-definability Church had proposed to him in a personal communication around February or March 1934. Thus, Gödel wrote on 15 February 1965 to Davis [in the offered letter], 'it is not true that footnote 3 is a statement of Church's Thesis. The conjecture stated there only refers to the equivalence of 'finite (computation) procedure' and 'recursive procedure'. However, I was, at the time of these lectures, not at all convinced that my concept of recursion comprises all possible recursions; and in fact the equivalence between my definition and Kleene's in Math. Ann. 112 (1936) is not quite trivial'" (quoted by Kleene, in ibid., p. 341). "Gödel was unconvinced by Church's thesis, since it did not rest on a direct conceptual analysis of the notion of finite algorithmic procedure . Indeed, in his Princeton lectures Gödel said that the notion of effectively computable function could serve just as a heuristic guide. It was only when Turing, in 1937, offered the definition in terms of his 'machines' that Gödel was ready to accept such an identification, and thereafter he referred to Turing's work as having provided the 'precise and unquestionably adequate definition of formal system' by his 'analysis of the concept of 'mechanical procedure' needed to give a general formulation of the incompleteness results'" (Fefermann in ibid., p. 33). As Gödel himself later wrote in a Postscriptum to the 1934 lectures, "if 'finite procedure' is understood to mean 'mechanical procedure', the question raised in footnote 3 can be answered affirmatively for recursiveness as defined in §9, which is equivalent with general recursiveness as defined today" (ibid., p. 370). In 1923-33, Alonzo Church presented a new system of logic. "At the time Church thought that his system - which he regarded as a 'radically different formulation of logic'- might escape the strictures of Gödel's incompleteness results, for he 'thought that Gödel['s] . theorem[s] might be found to depend on peculiarities of type theory,' a theory whose 'unfortunate restrictiveness' he sought to overcome. "By the fall of 1933 the consistency of Church's full formal system had begun to be suspect, and in the.

N° de réf. du vendeur 6293

Détails bibliographiques

• Titre: Typed letter signed 'Kurt Gödel' to Martin Davis, with manuscript annotations by both Gödel and Davis, on Gödel's contributions to Davis' book The Undecidable, and in particular Gödel's opinions on the 'Church-Turing thesis'
• Éditeur: The Institute for Advanced Study, Princeton, New Jersey
• Date de parution: 1965
• Édition: First edition.
• Catalogues du vendeur:
  • Computers, Numerical Methods
  • Mathematics, Analysis, Algebra