Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers (Google eBook)

Front Cover
Elsevier, Feb 4, 1992 - Computers - 667 pages
2 Reviews
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 !  

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

User Review  - Nick Black - Goodreads

Wish 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

Related books

Contents

Introduction
1
CHChapter I Recursiveness and Computability
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
Bibliography
603
Notation Index
643
IDXSubject Index
649
Copyright

Other editions - View all

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