Correspondence re Kleene's "Origins of recursive function theory" and Davis's "Why Gödel didn't have Church's thesis

Kleene, Stephen C. (1909-94); Martin Davis (1928-2023). (1) Group of 16 letters, including 8 typed letters signed and two autograph letters signed, pertaining to Kleene's 1981 paper, "Origins of recursive function theory," and Davis's 1982 paper, "Why Gödel didn't have Church's thesis"; see calendar of letters below. 26 sheets total. October 1981 - 19 February 1982. Very good.

(2) Kleene. Origins of recursive function theory. Offprint from Annals of the History of Computing 3 (1981). 52-67pp. 282 x 213 mm. Original plain wrappers. Very good. With 4 corrections in Kleene's hand.

"Kleene, along with Rózsa Peter, Alan Turing, Emil Post and others, is best known as a founder of the branch of mathematical logic known as recursion theory, which subsequently helped to provide the foundations of theoretical computer science. Kleene's work grounds the study of computable functions. A number of mathematical concepts are named after him: Kleene hierarchy, Kleene algebra, the Kleene star (Kleene closure), Kleene's recursion theorem and the Kleene fixed-point theorem. He also invented regular expressions in 1951 to describe McCulloch-Pitts neural networks, and made significant contributions to the foundations of mathematical intuitionism" (Wikipedia article on Kleene).

We are offering a collection of correspondence between Kleene and Martin Davis, a mathematician and logician who made important contributions to computability theory. Davis's work on Hilbert's tenth problem-asking for a general algorithm to decide the solvability of Diophantine equations-led to the Matiyasevich-Robinson-Davis-Putman (MRDP) theorem implying that a solution to this problem is impossible. Both Kleene and Davis had studied under Alonzo Church at Princeton, Kleene in the 1930s and Davis in the 1940s.

The correspondence offered here, consisting of 16 letters (see the calendar below), centers on Davis's paper, "Why Gödel didn't have Church's thesis" (Information and Control 54 [1982]: 3-24), which had been inspired by Kleene's 1979 lecture on "Origins of recursive function theory" given in San Juan, Puerto Rico in 1979 at the 20th annual IEEE Symposium on Foundations of Computer Science. In his letter of 11/14/79 (letter 1), Kleene proposed an addition to the published version of his lecture (Annals of the History of Computing 3 [1981]: 52-67), based on a suggestion by Davis:

"What would you think of adding the following to the second full paragraph of the of the right column of page 378: In a conversation at San Juan on October 31, 1979, Davis . . . expressed to me the opinion that my proof of the equivalence of my definition of general recursiveness to Gödel's (which Gödel called 'not quite trivial'), and my normal form theorem, were considerations which combined with Turing's arguments to convince Gödel of the Church-Turing thesis . . ."

Sometime in 1981 Davis sent Kleene a preliminary version of "Why Gödel didn't have Church's thesis"-a paper "directly stimulated by your San Juan lecture"-which outlined the development of -definability and recursive function theory by Gödel, Church, Turing, Kleene, Post and others in the 1930s. Davis asked for Kleene's comments and corrections to the paper (letter 2); Kleene ended up sending Davis two long letters (letters 4 and 9) with extensive criticisms and additions, clarifying the chronology and priority of discovery, and adding important historical detail, particularly with regard to Church and Gödel. An example:

"Just how far back Church's expressed speculations [re -definability] went I don't definitely recall. But his definite proposal was after his speaking out on the significance of -definability as a number-theoretic notion in the fall of 1933 . . . Then one day in his office in Fine Hall he made the definite proposal. This had to be after December 1933 since I was away from Princeton from early September 1933 till sometime in January or February 1934 . . . And Church, who is very careful, in his letter of November 29, 1935 (copy enclosed), written when his memory of the period should have been reasonably fresh, puts '[his] proposal that lambda-definability be taken as a definition of [effective calculability] ahead of Gödel's introduction of general recursiveness' (letter 4, 10/22/81).

Kleene's letter enclosed a photocopy of Church's 1935 letter (letter 6), in which Church described his and Kleene's development of -definability ("The notion of lambda-definability in its present form is, of course, the result of a gradual development . . . we seem to be agreed that the statement that the notion of lambda-definability is jointly due to you and me is fair . . .") and gave a brief history of "Gödel and the notions of recursiveness and effective calculability." In his letter of 11/16/81 (letter 9) Kleene supplied further information about Gödel's role vis-à-vis lambda-calculus and recursiveness theory, particularly his failure to credit Church's and Kleene's work:

"Now, I hate to say it. But I must acknowledge feeling that Gödel was somewhat less than generous in acknowledging (except only, so far as I know, for the footnote on your p. 72) a role of Church or me in three matters.

"In the spring term of 1934, Church had pushed -definability at a reluctant Gödel . . . Was it hard for Gödel to admit that Church had in fact been right (though not a persuasive as Turing later was), given Gödel's acceptance of Turing's equivalent?

"As my second illustration of Gödel's reluctance to give credit, Gödel has never to my knowledge taken any public notice of my having a role in generalizing his (first) incompleteness theorem . . .

"A third-rather trifling-illustration is the notion of 'partial recursive function.' I remember so vividly the words of Gödel on an occasion in Princeton in 1939-40 . . . when in a conversation with him I mentioned 'partial recursive functions' (terminology which, as you well know, I introduced in the J.S.L. in 1938). His exact words were, I swear, 'What is a partial recursive function?' . . . "(letter 9).

In this letter Kleene also stated that he would send Davis an offprint of "Origins of recursive function theory" in which "I am writing in four corrections" on pp. 52, 57, 59 and 60; this corrected offprint is included in the present collection. Davis gratefully incorporated Kleene's observations into the later drafts of his paper (letters 8 and 11), and Kleene responded with further minor corrections (letters 12, 13, 15 and 16).