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