Text books on computability

Question

I collected the following "top eight" text books on computability (in alphabetical order):

• Boolos et al., Computability and Logic

• Cooper, Computability Theory

• Davis, Computability and unsolvability

• Hermes, Enumerability, decidability, computability

• Hopcroft et al., Introduction to Automata Theory, Languages, and Computation
  (thanks to Bill Province)

• Kleene, Introduction to Metamathematics

• Minsky, Computation

• Sipser, Introduction to the Theory of Computation
  (thanks to Prajwal Kansakar)

I know it's opinion-based, but which important text books did I miss?

Answer 1

Hopcraft, Motwani and Ullman, Introduction to Automata Theory, Languages, and Computation

Answer 2

Michael Sipser, Theory of Computation. One of the best that is out there.

Answer 3

Cutland, Computability (CUP). A beautifully lucid and elegant classic text.

Answer 4

The following book is also quite famous I think:

Soare, R. (1987) Recursively enumerable sets and degrees

Here are two others about the interaction between computability and algorithmic randomness:

Nies, A. (2009) Computability and Randomness

Downey, R. Hirschfeldt, D. (2010) Algorithmic Randomness and Complexity

Answer 5

Some times ago, it was very popular :

• Hartley Rogers, Theory of Recursive Functions and Effective Computability (1967).

Answer 6

I'd say that [Odifreddi 1989] is still a good text to have, to use it at least as a reference book (but pretty good as a textbook too, I found).

One can also take a look at Peter Smith's "Teach yourself logic guide", where different sources are cited and commented upon. It covers much more than just computability, though there's a section exclusively on it (edit: now that I checked it again, there are actually two sections: 5.3 and 7.3 in the current version).

Answer 7

My undergraduate course, which was cross-listed with a graduate course, used Davis, Sigal, and Weyuker's Computability, Complexity, and Languages. It's billed as introductory, but I found it terse and I think it would be a very difficult introduction without a very good professor. However, it does cover a lot in a rigorous mathematical manner. I had the impression it was well regarded, but I don't see it mentioned much.

Answer 8

Soare's old book(mentioned above) is perhaps the most well known text about c.e. (formerly r.e.) languages.

Soare's new book, Turing Computability: Theory and Applications, is very dense but covers many areas and should be used as a refrence.

Answer 9

I would definitely add Godel, Escher, Bach (Hofstadter, 1979) to this list. It is a fascinating book that touches topics from computability, such as recursive and recursively enumerable sets / languages. I read GEB while taking a course on Computability and Complexity in university, and it was a great decision. Hofstadter does a great job explaining mind-boggling topics from computability theory and connecting them to seemingly unrelated stuff.