So, I was looking up some old threads, and I saw Robert Soare's Recursively Enumerable Sets and Degrees get a lot of Praise. However, I also saw the following textbooks be praised quite a bit:
- Michael Sipser, Theory of Computation
- N.J. Cutland, Computability
My question is which book should I use if I desire a comprehensive understanding of Computability, without any prior knowledge of the matter?
Soare's book goes far further than either Sipser or Cutland. I have various Opinions about the writing style and presentation, but it covers a lot of material you won't find in either book. For instance, Cutland's book is almost entirely contained in the first six chapters of Soare (the main exception being Godel's Theorem, which Soare treats as given if I recall correctly).
I think the biggest point of advantage of Soare over other texts is chapter VII: finite injury. This is a beautiful proof method, and resolves a deep question: are there any c.e. degrees other than $0$ and $0'$? The further chapters in Soare's book also cover material which is completely absent from Sipser and Cutland, but they won't be of deep interest to you unless you are really interested in the c.e. sets and degrees in particular.