Recursion Theory

by Joseph R. Shoenfield

Overview

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.

Product Details

ISBN-13:	9781107168084
Publisher:	Cambridge University Press
Publication date:	03/02/2017
Series:	Lecture Notes in Logic , #1
Pages:	92
Product dimensions:	6.14(w) x 9.25(h) x 0.43(d)

About the Author

Joseph R. Shoenfield works in the Department of Mathematics at Duke University, North Carolina.

Table of Contents

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.

Editorial Reviews

This paperback reprint of the more costly proceedings of 1993 allows researchers, teachers, and students of logic the potential to own a copy. The papers cover all areas of logic, with individual topics including: the geometry of U-rank 2 types, definability and global degree theory, the irreflexivity hypothesis for free left distributive magmas, labeled deductive systems, temporal expressive completeness in the presence of gaps, absoluteness for projective sets, and the structure of gamma degrees. The editors were part of the committee that brought the conference to their home institution of the U. of Helsinki in Finland. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews