## Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers (Google eBook)1988 marked the first centenary of Recursion Theory, since Dedekind's 1888 paper on the nature of number. Now available in paperback, this book is both a comprehensive reference for the subject and a textbook starting from first principles. Among the subjects covered are: various equivalent approaches to effective computability and their relations with computers and programming languages; a discussion of Church's thesis; a modern solution to Post's problem; global properties of Turing degrees; and a complete algebraic characterization of many-one degrees. Included are a number of applications to logic (in particular Gödel's theorems) and to computer science, for which Recursion Theory provides the theoretical foundation. |

### What people are saying - Write a review

Such an excellent book. Serves as an early but comprehensive introduction. It is the mark of a competent author to write with clarity whilst giving deep coverage of topics. Einstein's own writing in exposition of his theory is the case in point. Same is true of Russell on Foundations of Mathematics. The finest introductions are his, put the effort into the first 90 pages of Principia, and you will have a superb view of Russell's project. I wish this book was a little less pricey !

#### Review: Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers

User Review - Nick Black - GoodreadsWish I had this to prepare for the CS GRE come saturday, but even Amazon hasn't the power to get it to me by then. Oh well! I really doubt it (the test)'s going to get down and dirty into foundations ... Read full review

### Contents

1 | |

17 | |

CHChapter II Basic Recursion Theory | 125 |

CHChapter III Posts Problem and Strong Reducibilities | 251 |

CHChapter IV Hierarchies and Weak Reducibilities | 361 |

CHChapter V Turing Degrees | 447 |

CHChapter VI ManyOne and Other Degrees | 555 |

603 | |

643 | |

649 | |