Recursion Theory

A clear and focused introduction to recursion theory that is ideal for teaching and self-study.

Joseph R. Shoenfield (Author)

9781107168084, Cambridge University Press

Hardback, published 2 March 2017

92 pages
23.5 x 15.6 x 1.1 cm, 0.29 kg

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.

1. Computability
2. Functions and relations
3. The basic machine
4. Macros
5. Closure properties
6. Definitions of recursive functions
7. Codes
8. Indices
9. Church's thesis
10. Word problems
11. Undecidable theories
12. Relative recursion
13. The arithmetical hierarchy
14. recursively enumerable relations
15. Degrees
16. Evaluation of degrees
17. Large RE sets
18. Functions of reals
19. The analytical hierarchy
20. The projective hierarchy
Suggestions for further reading
Index.

Subject Areas: Mathematical theory of computation [UYA], Mathematical logic [PBCD]