8 typed letters signed to Martin Davis, plus 2 drafts of one of Davis's replies

Kleene, Stephen C. (1909-94); Martin Davis (1928-2023). Collection of correspondence and other materials, consisting of: (1) 8 typed letters signed from Kleene to Davis. 8 sheets total. 1950-52. (2) Autograph letter signed from Davis to Kleene plus 2 draft versions of another of Davis's letters to Kleene. 15 sheets total. 1951-52. (3) Davis. Some preliminary remarks on recursively enumerable sets. Typed and autographed draft. 25 sheets total. N.d. [1952]. (4) Rice, Henry Gordon (1920-2003). Classes of enumerable sets and their decision problems. Offprint from Transactions of the American Mathematical Society 74 (1953). 358-366pp. 255 x 179 mm. Original printed wrappers, vertically creased, light soiling. Some creasing, soiling and marginal fraying, but very good. Complete listing available. "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 (plus related materials) 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. In No. 1 (see the calendar below), dated 26 April 1950, Kleene warned Davis of an error in his (Kleene's) 1944 paper "On the forms of the predicates in the theory of constructive ordinals," and expresses "the hope that nothing in the part of your thesis concerning the transfinite extension of the hierarchy of predicate forms depends on my alleged theorem that a O is expressible in the form (x) (Ey) R (A, x, y) . . ." Nos. 2 - 7, written between March and October 1952, center on Davis's "Arithmetical problems and recursively enumerable predicates," a paper he had submitted earlier that year to the Journal of Symbolic Logic, of which Kleene was the editor. The JSL had sent the paper to a referee for review (per Kleene's letter to Davis of 18 April), which, as Davis informed Kleene, "is giving rise to one of those rather futile author-referee wrangles I have heard so much about . . . I replied to the original referee's report claiming that his proof was incorrect as I had been unable to fill in several gaps in his proposed argument. The referee counter-replied showing me how the gaps might be filled in; his argument now seems to me to be correct. There remain, then, two questions: 1) Is the referee's proof superior to mine? 2) If so, in what form should it be published? . . ." On 7 May Kleene replied that "we shall easily settle the author-referee wrangle . . . I shall simply submit the paper, together with the first referee's reports, to an experienced second referee and take his verdict." This 7 May letter (no. 5) also includes some discussion of Davis's work compared to Kleene's own: "In regard to publication of the material from the second section of your thesis, it is a little hard to advise you. For one thing, of course, there is some question of competition between your material and mine . . . Until I have seen the mimeographed student notes on the course which you are giving, I will not know whether your development is substantially different from developments that are in the literature or will be in the literature when and if I succe.…