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.
Previous Page Next Page