Algorithms for Constructing Computably Enumerable Sets
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 us...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Cham
Birkhäuser
2023, 2023
|
| Edition: | 1st ed. 2023 |
| Series: | Computer Science Foundations and Applied Logic
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer eBooks 2005- - Collection details see MPG.ReNa |
Table of Contents:
- 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