Recursion Theory

Description

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the first publication in the Lecture Notes in Logic series, Shoenfield gives a clear and focused introduction to recursion theory. The fundamental concept of recursion makes the idea of computability accessible to a mathematical analysis, thus forming one of the pillars on which modern computer science rests. This introduction is an ideal instrument for teaching and self-study that prepares the reader for the study of advanced monographs and the current literature on recursion theory. Contents......Page 8 1. Computability......Page 10 2. Functions and Relations......Page 11 3. The Basic Machine......Page 12 4. Macros......Page 14 5. Closure Properties......Page 17 6. Definitions of Recursive Functions......Page 20 7. Codes......Page 25 8. Indices......Page 29 9. Church's Thesis......Page 35 10. Word Problems......Page 37 11. Undecidable Theories......Page 41 12. Relative Recursion......Page 48 13. The Arithmetical Hierarchy......Page 52 14. Recursively Enumerable Relations......Page 57 15. Degrees......Page 62 16. Evaluation of Degrees......Page 68 17. Large RE Sets......Page 72 18. Functions of Reals......Page 76 19. The Analytical Hierarchy......Page 80 20. The Projective Hierarchy......Page 83 Suggestions for Further Reading......Page 88 Index......Page 90