Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers1988 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. |
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 | |
Common terms and phrases
Arithmetical Hierarchy axioms coding coinfinite comeager computation consider consistent construction contains countable defined definition disjoint distributive lattice e-splitting element elementarily equivalent equivalent Exercises existence extension finite set first-order Fixed-Point Theorem formal system formula function f given Gödel hence Hierarchy Hint holds hyperhypersimple hypersimple set induction infinite r.e. initial segment intersection isomorphic Jockusch Kleene Lemma m-degree minimal degrees natural numbers nonrecursive Note notion one-one open sets ordinals otherwise pair parameters partial functions partial ordering partial recursive function Post's Problem predicate primitive recursive primitive recursive function proof properties Proposition provable prove quantifiers r.e. sets Recursion Theory recursive sets recursive tree relation retraceable satisfied Second-Order Arithmetic semirecursive sequence set of degrees Set Theory simple set smallest strings strong minimal structure Suppose T-complete Turing degrees Turing machine undecidability uniform tree uppersemilattice variables