I had basic introduction to computability theory via Turing machines with some, rather basic, results. My background is a mixture of an undergraduate level math and cs. Now, I am looking for something more advanced, but still rather introductory/intermediate and gently paced. For example, I don't feel the need to jump right into something like Soare's Recursively Enumerable Sets and Degrees.
I have narrowed down my search for an optimal textbook to the following two titles:
- Computability: An Introduction to Recursive Function Theory by N.J. Cutland
- Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science by Davis, Sigal and Weyuker - this book also contains additional content like Automata theory, which is a nice bonus
I am interested in any of the following:
- Comparison of those two books (omitting parts in Davis's book like Grammars and Automata which are not in Cutland's book) and which one is by your opinion better.
- Opinion/review on one of the two mentioned books.
- Reference for another good introductury/intermediate level computability theory book.
Thank you for reading and for any kind of an opinion.
Cutland is quite excellent, in a slightly old-school way.
Barry Cooper's Computability Theory is also really very good.
For more, see the freely downloadable Beginning Mathematical Logic: A Study Guide, particularly pp 167--168.