1.4. Acknowledgements and References 7

The core material is in Chapters 3 through 7. In those, without

losing continuity, §§3.7, 4.5, 5.3, 6.2, and 6.3 may be omitted; if §6.2

is omitted, §5.4 may also be.

Chapters 8 and 9 should be covered as interest warrants. There

is no interdependence between sections of these chapters except that

§§9.4 and 9.5 both draw on §9.3, and §9.1 leans lightly on §8.3.

1.4. Acknowledgements and References

These notes owe a great debt to a small library of logic books. For

graduate- and research-level work I regularly refer to Classical Recur-

sion Theory by P. G. Odifreddi [68], Theory of Recursive Functions

and Effective Computability by H. Rogers [75], and Recursively Enu-

merable Sets and Degrees by R. I. Soare [82]. The material in here

owes a great deal to those three texts. More recently, I have enjoyed

A. Nies’ book Computability and Randomness [67]. As you will see,

M. Davis’ The Undecidable [18] was a constant presence on my desk

as well.

In how to present such material to undergraduates, I was influ-

enced by such books as Computability and Logic by Boolos, Burgess,

and Jeffrey [10], Computability by Cutland [17], A Mathematical In-

troduction to Logic by Enderton [25], An Introduction to Formal Lan-

guages and Automata by Linz [57], and A Transition to Advanced

Mathematics by Smith, Eggen, and St. Andre [81].

I have talked to many people about bits and pieces of the book,

getting clarifications and opinions on my exposition, but the lion’s

share of gratitude must go to Denis Hirschfeldt. Many thanks are due

also to the students in the three offerings of Computability Theory I

gave as I was writing this text, first as course notes and then with my

eye to publishing a book. With luck, their questions as they learned

the material and their comments on the text have translated into

improved exposition.