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

Front Cover
Elsevier, Feb 4, 1992 - Computers - 667 pages
1 Review
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

User Review - Flag as inappropriate

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 !  


CHChapter I Recursiveness and Computability
CHChapter II Basic Recursion Theory
CHChapter III Posts Problem and Strong Reducibilities
CHChapter IV Hierarchies and Weak Reducibilities
CHChapter V Turing Degrees
CHChapter VI ManyOne and Other Degrees
Notation Index
IDXSubject Index

Common terms and phrases

About the author (1992)

Piergiorgio Odifreddi is Professor of Mathematical Logic at the University of Turin and has been a visiting professor at Cornell University for many years. He is the author of the textbook "Classical Recursion Theory." He is also a regular contributor to the Italian daily "La Repubblica." Freeman Dyson, Professor Emeritus of Physics at the Institute for Advanced Study, is the author of several books, including "Disturbing the Universe.

Bibliographic information