Algorithms for Constructing Computably Enumerable Sets

I received an A.B. degree in linguistics from Cornell University in 1978, and a Ph. D. in computer science from the University of Illinois in 1981.  Then I worked three years for Hewlett-Packard in Palo Alto, California.  Subsequently, I taught for four years at Princeton University, and then 34 years at Ohio State University, where I retired in May, 2022, and now have emeritus status.  Along the way, I've consulted for IBM, AT&T, Hewlett-Packard, and various small companies.
My research has primarily been in the analysis of algorithms, however, I've long been fascinated by computability theory, which has been the focus of my research and much of my teaching in recent years.  In Autumn, 2021, I taught a graduate level course using an earlier draft of this book as the text..

1 Index of notation and terms.- 2 Set theory, requirements, witnesses.- 3 What's new in this chapter?.- 4 Priorities (a splitting theorem).- 5 Reductions, comparability (Kleene-Post Theorem).- 6 Finite injury (Friedberg-Muchnik Theorem).- 7 The Permanence Lemma.- 8 Permitting (Friedberg-Muchnik below C Theorem).- 9 Length of agreement (Sacks Splitting Theorem).- 10 Introduction to infinite injury.- 11 A tree of guesses (Weak Thickness Lemma).- 12 An infinitely branching tree (Thickness Lemma).- 13 True stages (another proof of the Thickness Lemma).- 14 Joint custody (Minimal Pair Theorem).- 15 Witness lists (Density Theorem).- 16 The theme of this book: delaying tactics.- Appendix A: a pairing function.- Bibliograph.- Solutions to selected exercises.

"The book is organized as a mathematics or theoretical computer science (CS) textbook. Theorems and lemmas, as well as pseudocode, demonstrate the solutions, and each chapter concludes with exercises. A very useful chapter summary describes the resultspresented in the chapter through a semiformal explanation." (Bálint Molnár, Computing Reviews, November 15, 2023)

“The book is organized as a mathematics or theoretical computer science (CS) textbook. Theorems and lemmas, as well as pseudocode, demonstrate the solutions, and each chapter concludes with exercises. A very useful chapter summary describes the resultspresented in the chapter through a semiformal explanation.” (Bálint Molnár, Computing Reviews, November 15, 2023)