Computability : An Introduction to Recursive Function Theory (Paperback)

Preface; Prologue, prerequisites and notation; 1. Computable functions; 2. Generating computable functions; 3. Other approaches to computability: Church’s thesis; 4. Numbering computable functions; 5. Universal programs; 6. Decidability, undecidability and partical decidability; 7. Recursive and recursively enumerable sets; 8. Arithmetic and Godel’s incompleteness theorem; 9. Reducibility and degrees; 10. Effective operations on partial functions; 11. The second recursion theorem; 12. Complexity of computation; 13. Further study.