Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1 (Studies in Logic and the Foundations of Mathematics, Vol. 125) [Hardcover]

Piergiorgio Odifreddi (Author)

Book Description

ISBN-10: 0444872957 | ISBN-13: 978-0444872951 | Publication Date: March 1989

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 Godel's theorems) and to computer science, for which Recursion Theory provides the theoretical foundation.

Editorial Reviews

Review

Rodney G. Downey
The scope of the material is amazing. For instance, I can think of no other book with a treatment of w-REA sets inductive reference, and models of lambda calculus! This is especially gratifying in a world of continuing mathematical fragmentation.
Mathematical Reviews
--This text refers to an alternate Hardcover edition.

Product Details

• Hardcover: 686 pages
• Publisher: North-Holland (March 1989)
• Language: English
• ISBN-10: 0444872957
• ISBN-13: 978-0444872951
• Product Dimensions: 9.2 x 6.5 x 1.5 inches
• Shipping Weight: 2.6 pounds
• Average Customer Review: 3.5 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #10,624,143 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

11 of 13 people found the following review helpful:

3.0 out of 5 stars Interesting but very uneven, July 11, 2005

By 

Nathan Oakes (Ashland, Oregon) - See all my reviews

This review is from: Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1 (Studies in Logic and the Foundations of Mathematics, Vol. 125) (Paperback)

The stated goal of the book is to have no prerequisites other than freshman math, but you really need at least undergrad logic and set theory. It is a thick book and covers a lot of interesting stuff, but there can be a frustrating lack of order and detail. He is an engaging writer, but sloppy in that he gives only part of the information you need to understand something, forgetting that he didn't give it or you don't know it. Sections are often either too sketchy or wordy and unfocused. Sometimes, though, he comes through with an elegant explanation of something. He is at his best when relating recursion theory to science, philosophy, and other branches of math. These discussions tend to be rather handwavy, but he gives references to the literature. The book as a whole is not very unified and it doesn't clearly indentify and relate the central ideas of recursion theory, so it wouldn't make a good introductory text. But it is a good reference for those with a moderate background.

4 of 4 people found the following review helpful:

4.0 out of 5 stars better as a reference book than as a textbook, March 9, 2008

By 

a reader (Taipei) - See all my reviews

This review is from: Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1 (Studies in Logic and the Foundations of Mathematics, Vol. 125) (Paperback)

I agree with much of what another reviewer has said (July 11, 2005 ). But I don't think that Odifreddi has exaggerated when he claims that the prerequisites of reading his book will be roughly freshman math. Having said that, I admit that since many students in their sophomore year still don't possess a working knowledge of, say proof by mathematical induction, the book is certainly too heavy for those readers. Further aggravating the difficulty for beginners is the book's admittedly less-than-ideal organization and presentation of some portion of the enormously many topics it treats. This will be frustrating for readers who are not enthusiasts of the book's multifarious viewpoints and prefer a quick introduction to the subject instead. I recommend N.Cutland's "Computability" to newcomers. Nevertheless, for those who plan a future career in mathematical logic, especially recursion theory, Odifreddi's book will prove to be a treasure trove of unusual and stimulating insights not easily encountered elsewhere - even though one might not always agree with his ideas. For the future logicians I also recommend R.Soare's "Recursively enumerable sets and degrees" for a deeper treatment of r.e. sets.