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

P. Odifreddi

Feb 1992 · Elsevier

About this 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.

Ratings and reviews

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 !