Recursion Theory

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

List 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.

About the author

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

Summary

An introduction to recursion theory that will prepare the reader for the study of advanced monographs and the current literature on the topic. The clarity and focus of this text makes it an ideal instrument for teaching and self-study.

Product details

• Authors: Joseph R. Shoenfield, Joseph R. (Duke University Shoenfield
• Publisher: Cambridge University Press ELT
• Languages: English
• Product format: Hardback
• Released: 02.03.2017
• EAN: 9781107168084
• ISBN: 978-1-107-16808-4
• No. of pages: 92
• Series: Lecture Notes in Logic
• Subject: Natural sciences, medicine, IT, technology > Mathematics > Basic principles