Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
Thanks! Everything you wrote is actually quite helpful. I should mention that at some point I read Cutland, which I found extremely "easy" (but still very interesting and helpful). So I will probably just read Soare. I would have liked a text that felt more introductory (i.e. with motivation, even if it repeated what I read in Cutland). I feels like the "real point" of Soare is parts C and D, so I thought there might've been something covering A and B in more detail. – user8772 Mar 28 '11 at 16:08

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
Siper's book is, unfortunately, not very appropriate for the material that is called "computability" in mathematical logic. This is not to say it's a bad book, it simply has a different focus. It does a good job of covering aspects of computable sets, but has very little material on uncomputable sets other than the halting problem. It doesn't cover fundamental topics such as the arithmetical hierarchy and Post's theorem, nor does it construct (as far as I remember) any intermediate c.e. set, nor does it have any priority arguments. So it's probably not the book this person is looking for. – Carl Mummert Mar 28 '11 at 10:58

I found video lectures that were given at the University of Colorado Boulder in the Spring of 2011 by Bart Kastermans. The syllabus includes the material you mentioned and:

Lecture 24 Finite injury, showing the existence of a low simple set.

Lecture 27 Infinite Injury and the Thickness Lemma.

Lecture 31 Density Theorem

For a person that learns alone, it is useful to see how other mathematicians treat the concepts, hence the videos may be a good supplement to the learning material. For 0''' priority method, Soare is still the best source.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.