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

by Piergiorgio Odifreddi

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

Genres: Mathematics, Logic, Reference

688 pages, Paperback

First published February 4, 1992

About the author

Piergiorgio Odifreddi is an Italian mathematician, logician and aficionado of the history of science, who is also extremely active as a popular science writer and essayist, especially in a perspective of philosophical atheism as a member of the Italian Union of Rationalist Atheists and Agnostics.

Reviews

[Matthieu · Rating 4 out of 5]

I: First, let's get something out of the way: the following volume is even better. While Odifreddi does a fine job of introducing set-functional and set-theoretic groups, the next volume fleshes out the material in a way that seems much more intuitive.

II: Recursion theory is fascinating. Prior to taking a course back in the autumn, I knew very little about it (outside of Grant and Ayer's work, which, by now, is hopelessly outdated). Our class was to use this book as a supplementary text (should we find ourselves moving too quickly through the main text, or if we wanted a more rigorous (and elegant!) vision of CRT that was decidedly less user-friendly. I found the main text (Olson) to be too stuffy (full of superfluous, seemingly useless information), so the Odifreddi was a pleasant change.

III: Being the first volume, we're dealing with the foundations of the field. As I mentioned earlier, the second volume is the best place to start for someone already familiar with s-f/s-t groups. While it could serve as a refresher of sorts, one would be better off reviewing problem sets, consulting course notes, etc. Too much of it would seem introductory (which makes sense, because it is).

IV: Coming from a physics and (pure) mathematics background, the thought of breaking into computer science was enticing, though I was hesitant, as I was already spread thin, and felt that it would be foolish to venture into a new, almost exotic field if I didn't have the time for thorough investigations. However, after a short period of deliberation, I decided to take the course (concurrently with a mathematical logic course, I might add), and it was worth it.

V: The fluidity of the (apparent) overlapping of rigorous ('crystal box') mathematical logic and (clean, open-ended) theoretical computer science is a beautiful, beautiful thing.

VI: Turing reductions are little jewels. Sealed boxes.

VII: It's rather expensive, especially if you buy both volumes at once. The cost (and introductory nature) is the reason for the four stars.

VIII: Minor issues aside, Odifreddi did a marvelous job here. Worthy of main text status, for sure.

[Nick Black]

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 of computation, but I've never even read Rogers's Theory of Recursive Functions and Effective Computability, and found Sorbi too difficult to bother with at the time...:/ ugh!

[Peter Gerdes · Rating 5 out of 5]

This (and the even better sequel) are THE reference works in recursion theory. This book is more focused on the early work in the field. Measures of complexity, hierarchies of fast growing functions, inductable classes of functions, r.e. degrees, m-degrees, creative, simple, and hypersimple sets. Some stuff on Turing degrees as well but primarily about degrees around 0' (jump inversion etc..).

If you do recursion theory buy this book even if you have to search the earth for it but you might want to buy the second volume first if you can't afford both at once.