دانلود کتاب Algorithms for Constructing Computably Enumerable Sets

فهرست مطالب :

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