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 succeed in getting my book [Introduction to Metamathematics] published . . ." On 4 June (No. 6) Kleene informed Davis that "I now have the second referee's report on your paper . . . I am returning the manuscript to you, for you to revise in accordance with the referee's suggestions." On 2 October, per Kleene's letter of that date (No. 7), Davis's paper was sent to the first referee for a final check.

Nos. 8 - 12, written in January and February 1952, concern a report that Davis was preparing at Kleene's request on H. G. Rice's "Classes of recursively enumerable sets and their decision problems," a paper Rice had submitted to the JSL. "You will recall that I mentioned to you at the Bryn Mawr meetings (or was it Providence?) that, owing to the fact our pages are very crowded now, and the length of the paper of H. G. Rice, we may wish to transfer it. Under these circumstances it is embarrassing to us to hold it too long before raising this question with the author . . . Could I have [your] report within the next week . . ." (letter of 29 January).

Davis replied on 3 February: "Although I told you at Providence, that I would let you have my report very soon, I am afraid that it is not yet ready. There are two reasons for this. The first of these is that my initial reading of the paper convinced me that it should be revised considerably before publication. As a result a more detailed report will be required than would ordinarily have been necessary . . ." By 18 February, per Kleene's letter of that date (no. 12), Davis had sent in his "exceedingly careful and thorough report" (No. 11), which recommended that Rice's paper "be rewritten with Parts II and IV omitted." A copy of Rice's paper is included with this collection.