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