Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1

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

[Nick Black · Rating 5 out of 5]

(2010)
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!
---
(2026)
OK, fifteen plus years later i finally got around to these 940 pages, and...they're unexpectedly fantastic. a complete and authoritative introduction to recursion theory from the very bottom (axiom schemes, construction of the integers) to pretty goddamn far up, well beyond anything i'd seen before (a thorough study of degree theory). it is furthermore marked throughout by clarity, wit, and wide-ranging reference. how often do you see things like this in a thousand page math book?

As a whole, this introductory chapter (and the first two sections of the next one) may be thought of as a technical version of what Webb [1980] does philosophically and Hofstadter [1979] pyrotechnically.

now reading this over once more, perhaps it is not as sideachingly funny as i first thought, but i assure you this is about as droll as it gets in the world of STUDIES IN LOGIC AND THE FOUNDATIONS OF MATHEMATICS.

Chapter 1: basic computability including λ-calc. you ought know all of this from undergraduate. if you don't, you're probably going to have a bad time. still, it's well worth reading for odifreddi's superb presentation, and several results caught me by surprise.

Chapter 2: basic recursion theory. you likewise saw most of this back when you were poring over sipser ( Introduction to the Theory of Computation), though not in this depth. honestly, sipser is about the minimal possible depth one can do.

Chapter 3: post's problem and strong reducibilities. if you liked kinda grokking post's problem you're going to love getting blasted in the face with post's problem and everything that can reduce to it. think of Garey & Johnson ( Computers and Intractability) but for r.e. languages.

Chapter 4: hierarchies and weak reducibilities. remember reading scott aaronson's "Polynomial Hierarchy Collapses", and chuckling nervously because you didn't quite get it, but knew it was funny? you will now get it.

Chapters 5 and 6: degree theory out the ass. i honestly skimmed most of this, being not terribly interested in degree theory, and having only one life to live, and there being a second volume even longer than this one. everything looked to be executed at the same (almost unbelievably) high level of quality as the preceding four chapters.

this book is an incredible achievement that maybe ten people worldwide will read this year. will it help you be a better software engineer? almost certainly not. will it help make you a better person? ehh, likewise dubious. will you finally understand everything that your undergraduate computer science education kinda handwaved over? well, certainly not everything; undergraduate programs are prone to handwavery and growing still more prone every year. will you know classical recursion theory? like a fucking boss you will.

i bestow upon Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1 (Studies in Logic and the Foundations of Mathematics, Vol. 125) the DANK SEAL OF QUALITY and consider it fun for the whole family.

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

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