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-
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
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