Kurt Gödel

As far as the second half of section (3) is concerned, 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 is not quite trivial." Provenance: American mathematician Dr. Martin Davis received his doctorate at Princeton University where his adviser was Alonzo Church. Davis is best known for his work on Hilbert's tenth problem as well as for pioneering work on the so-called "satisfiability problem." Davis edited the 1965 publication The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, which included 5 pieces by Gödel as well as material by Alan Turing, Alonzo Church, Emil Post, Stephen K. Kleene and J.B. Rosser. Kurt Gödel, who was a friend and colleague of Albert Einstein, has been considered one of the most important logicians since Aristotle who, according to Dr. Davis, "utterly transformed the field of mathematical logic and our understanding of the foundations of mathematics, starting with his famous 'incomplete theorem.'" Davis recounts the context of the above material: "As a young man committed to making mathematical logic my life's work, Gödel was a towering and inspirational figure. I was also thrilled to be part of the circle at the Institute for Advanced Studies at Princeton, and to see Einstein and Gödel walking together. Many years later, I was editing an anthology of fundamental research papers, The Undecidable (1965), all concerned with the new perspectives that Gödel's revolutionary 1931 paper on formally undecidable propositions had illuminated. Several of the articles included were by Gödel himself. The book was entirely in English although three of Gödel's contributions had been originally published in German, and I translated two of these. I was pleased when during our correspondence he approved my translations. He also wrote me adding a significant amount of new material to another article (one that had originated in a series of lectures given in English at the Institute of Advanced Study in Princeton in 1934), bringing it up to date, emphasizing the importance of Alan Turing's work in extending the incompleteness theorem. Gödel sent some of this material to me in a handwritten letter, explaining that, because he was ill, he'd been unable to have it typewritten. After Gödel's death in 1978, I was studying a manuscript found with his effects for a project to publish his collected works. I was amazed to discover in it work by Gödel that was very close in method and form to a theorem in my doctoral dissertation of 1950 that had enabled a strengthened form of the incompleteness theorem." In his book The Universal Computer, Dr. Davis summarized what Gödel had done with his paper on undecidability, the centerpiece of the Davis edited book The Undecidable: "Leibniz had certainly proposed the development of a precise artificial language in which much human thought would be reduced to calculation. Frege, in his Bgriffsschrift, had shown how the usual logical reasoning by mathematicians could indeed be captured. Whitehead and Russell had succeeded in developing actual mathematics in an artificial language of logic. Hilbert had proposed the metamathematical study of languages. But before Gödel no one had shown how these metamathematical concepts could be embedded in the languages themselves" (p 121)..