Computability Theory: An Introduction to Recursion Theory provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The text includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable way.
1. Cover Image 2. Table of Contents 3. Front Matter 4. Copyright 5. Dedication 6. Foreword 7. Preface 8. 1. The Computability Concept 9. 1.1. The Informal Concept 10. 1.2. Formalizations – an Overview 11. 2. General Recursive Functions 12. 2.1. Primitive Recursive Functions 13. 2.2. Search Operation 14. 3. Programs and Machines 15. 3.1. Register Machines 16. 3.2. A Universal Program 17. 3.3. Register Machines Over Words 18. 3.4. Binary Arithmetic 19. 4. Recursive Enumerability 20. 4.1. Recursively Enumerable Relations 21. 4.2. Parameters 22. 5. Connections to Logic 23. 5.1. Arithmetical Hierarchy 24. 5.2. Definability in Arithmetic 25. 5.3. The Complexity of Truth 26. 6. Degrees of Unsolvability 27. 6.1. Relative Computability 28. 6.2. Equivalence Relations 29. 6.3. Preordering Relations 30. 6.4. Ordering Degrees 31. 6.5. Structure of the Degrees 32. 7. Polynomial-Time Computability 33. 7.1. Feasible Computability 34. 7.2. P versus NP 35. 7.3. Some Other Complexity Classes 36. A1. Mathspeak 37. A2. Countability 38. A3. Decadic Notation 39. References 40. Index
Computability Theory: An Introduction to Recursion Theory provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The text includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable way.
1. Cover Image 2. Table of Contents 3. Front Matter 4. Copyright 5. Dedication 6. Foreword 7. Preface 8. 1. The Computability Concept 9. 1.1. The Informal Concept 10. 1.2. Formalizations – an Overview 11. 2. General Recursive Functions 12. 2.1. Primitive Recursive Functions 13. 2.2. Search Operation 14. 3. Programs and Machines 15. 3.1. Register Machines 16. 3.2. A Universal Program 17. 3.3. Register Machines Over Words 18. 3.4. Binary Arithmetic 19. 4. Recursive Enumerability 20. 4.1. Recursively Enumerable Relations 21. 4.2. Parameters 22. 5. Connections to Logic 23. 5.1. Arithmetical Hierarchy 24. 5.2. Definability in Arithmetic 25. 5.3. The Complexity of Truth 26. 6. Degrees of Unsolvability 27. 6.1. Relative Computability 28. 6.2. Equivalence Relations 29. 6.3. Preordering Relations 30. 6.4. Ordering Degrees 31. 6.5. Structure of the Degrees 32. 7. Polynomial-Time Computability 33. 7.1. Feasible Computability 34. 7.2. P versus NP 35. 7.3. Some Other Complexity Classes 36. A1. Mathspeak 37. A2. Countability 38. A3. Decadic Notation 39. References 40. Index
