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.
Author(s): Joseph R. Shoenfield
Series: Lecture Notes in Logic 1
Publisher: Cambridge University Press
Year: 2017
Language: English
Pages: 93
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
