6 1. Introduction intuitive notion in terms of which problems of this class are often stated, and to show, by means of an example, that not every problem of this class is solv- able. Church’s major contribution here is the point that we need some formal notion of “finite process” to answer Hilbert. He proposes two options in this paper: the lambda calculus, due to him and Kleene, and recursive functions, defined originally by odel [30] (after a sug- gestion by Herbrand) and modified by Kleene. Shortly thereafter Kleene proposed what we now call the partial recursive functions [44]. It was not widely accepted at the time that any of these definitions was a good characterization of “effectively computable,” however. It was not until Turing developed his Turing machine [85], which was accepted as a good characterization, and it was proved that Turing- computable functions, lambda-computable functions, and partial re- cursive functions are the same class, that the functional definitions were accepted. All three of these formalizations of computability are studied in Chapter 3. The idea that not all problems are solvable comes up in Chapter 4, along with many of the tools used in such proofs. Both odel’s Incompleteness Theorem and Church’s unsolvability result treat the limitations of mechanical, or algorithmic, procedures in mathematics. As is common in mathematics, these new ideas and tools took on a life of their own beyond answering Hilbert or finding the major flaw in Russell and Whitehead’s approach to mathematics. The new field became known as recursion theory or computability theory. Chapters 5–8 explore some of the additional topics and fun- damental results of the area, and Chapter 9 contains a survey of some areas of current interest to computability theorists. 1.3. Notes on Use of the Text My intent is that Chapter 2 will be covered on an as-needed basis, and I have tried to include references to it wherever applicable throughout the text. However, the vocabulary in §§2.1 and 2.2 is needed through- out, so they should be read first if unfamiliar. Returning to §1.1 after reading through Chapter 4 may be helpful as well.
Previous Page Next Page