## Recursion Theory

Joseph R. Shoenfield

Year: 2001

ISBN: 1-56881-149-7

96 pages. Paperback.

Buy now

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.

### Table of Contents

- Computability
- Functions and Relations
- The Basic Machine
- Macros
- Closure Properties
- Definitions of Recursive Functions
- Codes
- Indices
- Church’s Thesis
- Word Problems
- Undecidable Theories
- Relative Recursion
- The Arithmetical Hierarchy
- Recursively Enumerable Relations
- Degrees
- Evaluation of Degrees
- Large RE Sets
- Functions of Reals
- The Analytical Hierarchy
- The Projective Hierarchy