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

Description

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 History This Book Acknowledgements A Truth Universally Acknowledged Contents 1 Notation and Terms 1.1 Index of Notation and Terms 1.2 Defaults 1.3 Notes About the Pseudo-code 1.4 Miscellaneous Notes About the Text 2 Set Theory, Requirements, Witnesses 2.1 Diagonalization 2.2 Infinitely Many Infinite Cardinals 2.3 What's New in This Chapter? 2.4 Exercises 3 Computable and c.e. Sets 3.1 Turing Machines 3.2 Computably Enumerable, Computable, c.e.n 3.3 An Example of a c.e.n. Set 3.4 What's New in This Chapter? 3.5 Afternotes 3.6 Exercises 4 Priorities (A Splitting Theorem) 4.1 A Priority Argument 4.2 What's New in This Chapter? 4.3 Afternotes 4.4 Exercises 5 Reductions, Comparability (Kleene-Post Theorem) 5.1 Oracle Turing Machines 5.2 Turing Reductions 5.3 The Theorem 5.4 What's New in This Chapter? 5.5 Afternotes 5.6 Exercises 6 The Permanence Lemma 6.1 Notation 6.2 The Lemma 6.3 Afternotes 6.4 Exercises 7 Finite Injury (Friedberg-Muchnik Theorem) 7.1 The Theorem 7.2 What's New in This Chapter? 7.3 Afternotes 7.4 Exercises 8 Permitting (Friedberg-Muchnik Below C Theorem) 8.1 The Lemma 8.2 The Theorem 8.3 Valid Witnesses 8.4 Types of Witnesses 8.5 The Algorithm 8.6 Verification 8.7 What's New in This Chapter? 8.8 Afternotes 8.9 Exercises 9 Length of Agreement (Sacks Splitting Theorem) 9.1 The Idea 9.2 The Theorem 9.3 Definitions 9.4 The Algorithm 9.5 Verification 9.6 Why Preserve Agreements? 9.7 What's New in This Chapter? 9.8 Afternotes 9.9 Exercises 10 Introduction to Infinite Injury 10.1 A Review of Finite Injury Priority Arguments 10.2 Coping with Infinite Injury 10.2.1 Guessing 10.2.2 Other Methods 11 A Tree of Guesses (Weak Thickness Lemma) 11.1 The ``Lemma'' 11.2 The Tree 11.3 Definitions 11.4 The Algorithm 11.5 Verification 11.6 What's New in This Chapter? 11.7 Afternotes 11.8 Exercises 12 An Infinitely Branching Tree (Thickness Lemma) 12.1 The Tree 12.2 Definitions, and a Fact 12.3 The Algorithm 12.4 Verification 12.5 What's New in This Chapter? 12.6 Afternotes 12.7 Exercises 13 Joint Custody (Minimal Pair Theorem) 13.1 The Theorem 13.2 The Tree, and an Overview of Our Strategy 13.3 Definitions 13.4 Interpretation of the Guesses 13.5 The Algorithm 13.6 Verification 13.7 What's New in This Chapter? 13.8 Afternotes 13.9 Exercises 14 Witness Lists (Density Theorem) 14.1 The Tree 14.2 Definitions 14.3 The Algorithm 14.3.1 Main Code 14.3.2 Subroutines 14.3.3 Notes on the Algorithm 14.4 Verification 14.4.1 More Definitions 14.4.2 Interpretation of the Guesses 14.4.3 Facts 14.4.4 Lemmas 14.5 What's New in This Chapter? 14.6 Designing an Algorithm 14.7 Afternotes 14.8 Exercises 15 The Theme of This Book: Delaying Tactics Appendix A A Pairing Function Appendix Bibliography 1 Books 2 Articles Appendix Solutions to Selected Exercises