Algorithms for Constructing Computably Enumerable Sets (Computer Science Foundations and Applied Logic)

Logicians have developed beautiful algorithmic techniques for the construction of computably enumerable sets. This textbook presents these techniques in a unified way that should appeal to computer scientists. Specifically, the book explains, organizes, and compares various algorithmic techniques used in computability theory (which was formerly called "classical recursion theory"). This area of study has produced some of the most beautiful and subtle algorithms ever developed for any problems. These algorithms are little-known outside of a niche within the mathematical logic community. By presenting them in a style familiar to computer scientists, the intent is to greatly broaden their influence and appeal. Topics and features: · All other books in this field focus on the mathematical results, rather than on the algorithms. · There are many exercises here, most of which relate to details of the algorithms. · The proofs involving priority trees are written here in greater detail, and with more intuition, than can be found elsewhere in the literature. · The algorithms are presented in a pseudocode very similar to that used in textbooks (such as that by Cormen, Leiserson, Rivest, and Stein) on concrete algorithms. · In addition to their aesthetic value, the algorithmic ideas developed for these abstract problems might find applications in more practical areas. Graduate students in computer science or in mathematical logic constitute the primary audience. Furthermore, when the author taught a one-semester graduate course based on this material, a number of advanced undergraduates, majoring in computer science or mathematics or both, took the course and flourished in it. Kenneth J. Supowit is an Associate Professor Emeritus, Department of Computer Science & Engineering, Ohio State University, Columbus, Ohio, US. Preface 7 History 7 This Book 7 Acknowledgements 9 A Truth Universally Acknowledged 9 Contents 11 1 Notation and Terms 15 1.1 Index of Notation and Terms 15 1.2 Defaults 19 1.3 Notes About the Pseudo-code 20 1.4 Miscellaneous Notes About the Text 20 2 Set Theory, Requirements, Witnesses 21 2.1 Diagonalization 22 2.2 Infinitely Many Infinite Cardinals 23 2.3 What's New in This Chapter? 24 2.4 Exercises 25 3 Computable and c.e. Sets 26 3.1 Turing Machines 26 3.2 Computably Enumerable, Computable, c.e.n 29 3.3 An Example of a c.e.n. Set 32 3.4 What's New in This Chapter? 34 3.5 Afternotes 34 3.6 Exercises 34 4 Priorities (A Splitting Theorem) 36 4.1 A Priority Argument 36 4.2 What's New in This Chapter? 41 4.3 Afternotes 41 4.4 Exercises 42 5 Reductions, Comparability (Kleene-Post Theorem) 44 5.1 Oracle Turing Machines 44 5.2 Turing Reductions 46 5.3 The Theorem 47 5.4 What's New in This Chapter? 51 5.5 Afternotes 52 5.6 Exercises 52 6 The Permanence Lemma 54 6.1 Notation 54 6.2 The Lemma 55 6.3 Afternotes 56 6.4 Exercises 56 7 Finite Injury (Friedberg-Muchnik Theorem) 58 7.1 The Theorem 58 7.2 What's New in This Chapter? 61 7.3 Afternotes 62 7.4 Exercises 62 8 Permitting (Friedberg-Muchnik Below C Theorem) 64 8.1 The Lemma 64 8.2 The Theorem 65 8.3 Valid Witnesses 66 8.4 Types of Witnesses 67 8.5 The Algorithm 68 8.6 Verification 69 8.7 What's New in This Chapter? 72 8.8 Afternotes 72 8.9 Exercises 73 9 Length of Agreement (Sacks Splitting Theorem) 74 9.1 The Idea 74 9.2 The Theorem 76 9.3 Definitions 77 9.4 The Algorithm 78 9.5 Verification 78 9.6 Why Preserve Agreements? 82 9.7 What's New in This Chapter? 84 9.8 Afternotes 84 9.9 Exercises 85 10 Introduction to Infinite Injury 86 10.1 A Review of Finite Injury Priority Arguments 86 10.2 Coping with Infinite Injury 87 10.2.1 Guessing 87 10.2.2 Other Methods 88 11 A Tree of Guesses (Weak Thickness Lemma) 90 11.1 The ``Lemma'' 90 11.2 The Tree 92 11.3 Definitions 97 11.4 The Algorithm 99 11.5 Verification 100 11.6 What's New in This Chapter? 107 11.7 Afternotes 108 11.8 Exercises 108 12 An Infinitely Branching Tree (Thickness Lemma) 112 12.1 The Tree 112 12.2 Definitions, and a Fact 113 12.3 The Algorithm 115 12.4 Verification 115 12.5 What's New in This Chapter? 121 12.6 Afternotes 122 12.7 Exercises 122 13 Joint Custody (Minimal Pair Theorem) 125 13.1 The Theorem 126 13.2 The Tree, and an Overview of Our Strategy 127 13.3 Definitions 128 13.4 Interpretation of the Guesses 129 13.5 The Algorithm 129 13.6 Verification 130 13.7 What's New in This Chapter? 134 13.8 Afternotes 134 13.9 Exercises 135 14 Witness Lists (Density Theorem) 137 14.1 The Tree 138 14.2 Definitions 138 14.3 The Algorithm 142 14.3.1 Main Code 143 14.3.2 Subroutines 143 14.3.3 Notes on the Algorithm 144 14.4 Verification 146 14.4.1 More Definitions 147 14.4.2 Interpretation of the Guesses 148 14.4.3 Facts 148 14.4.4 Lemmas 160 14.5 What's New in This Chapter? 169 14.6 Designing an Algorithm 170 14.7 Afternotes 171 14.8 Exercises 172 15 The Theme of This Book: Delaying Tactics 174 Appendix A A Pairing Function 175 Appendix Bibliography 176 1 Books 176 2 Articles 177 Appendix Solutions to Selected Exercises 179