Recursion theory text, alternative to Soare

Question

I want/need to learn some recursion theory, roughly equivalent to parts A and B of Soare's text. This covers "basic graduate material", up to Post's problem, oracle constructions, and the finite injury priority method. Is there an alternate, more beginner friendly version of this material in another text? (At a roughly senior undergraduate or beginning graduate level of difficulty, although I wouldn't necessarily mind easier.)

For example, one text I've seen is S. Barry Cooper's book, Computability Theory. Is there anybody that has read both this and Soare, and could tell me about their similarities/differences?

Answer 1

A popular introductory textbook that covers both computability and complexity is Michael Sipser's "Introduction to the Theory of Computation". The computability section concludes with a nice chapter on advanced computability issues.

Answer 2

You're in a difficult situation: you're interested in material that is usually taught at the graduate level, but you want a book written at a lower level. That's a common problem for students in mathematics, and there's usually no easy fix. Most undergraduate-level books on computability only go through the halting problem, and then stop. Cutland's textbook, which I think is a very good undergraduate book, is an example of this.

Soare's book is the standard textbook in computability at the moment (if there is such a thing as a standard textbook). It's a beginning graduate-level book, which means it doesn't require any previous knowledge of computability, just a significant investment of effort to learn the material. Most graduate-level books will require a lot of careful reading and rereading, along with working exercises, to learn the material. That's simply the way things are.

Cooper's book is written in a way that makes the material feel much more accessible, like an advanced undergraduate level. I think it does a good job of presenting the way that computability theorists think about the area, and the book has a much larger selection of topics than other books written at a similar level. However, it does this by omitting many details, which you would have to work out for yourself. There is a risk, with books of this sort, that you may have a false confidence in your understanding of the material. Soare's book is much more fastidious about details. In the end, using Cooper's book would require just as much effort as Soare's book, except that you would have to work out the proof details for yourself.

My recommendation would be to read Cooper's book to get an idea what's going on, and to get a general idea, then dig into Soare's book to learn the proofs in detail.

There is also a classic text by Rogers, which is well regarded. Although the book is a little old, the material on computability and priority arguments is very well written and still perfectly applicable today.

Answer 3

For a sped up introduction, you could try 'Theory of Computation' by Dexter Kozen. Lectures 33 onwards it looks at some recursion theory, so it might help you become comfortable with things before you start with the heavier stuff. It is possible though that it won't cover all the material you are looking for (not with sufficient detail in any case). But still, it is a pleasant read, and there are also some nice exercises at the end.

Answer 4

Just to mention, Enderton has recently published a textbook called Computability Theory. I have not read this so I don't know how it is.

Also Odiffredi has written Classical Recursion Theory Volume 1 and 2. These two huge book contain more material than any other textbook in Computability Theory. It also like an encyclopedia. I have never used it as a textbook, but it is very good for reference - you can learn about Quasicreastive sets here. In terms of topics, I think he has even greater diversity of topics that Cooper. Just looking in the table of content I see things like probabalistic physics, computer and thought, the brain, .... Volume II even does some complexity theory.

Also, in my opinion Computability theory is more than just learning some results. Alot of Computability Theory is about various methods (permitting, finite injury, infinite injury, tree, etc) of constructing various sets or degrees. The portion of the book you mentions (up to finite injury) is pretty good for learning how to do these constructions. Working thought Soares's book and doing the exercises is a good way to understand these construction method well enough to be able to do one yourself.