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 G¨ 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 G¨ 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.