Here is a selection of textbooks about Computability and Complexity theory.

Kozen.jpg

Automata and Computability

Dexter Kozen

Springer Verlag

Clear and concise.

Sipser.jpg

Introduction to the Theory of Computation (3rd ed.)

Michael Sipser

Cengage Learning

Must have.

Boolos.jpg

Computability and Logic (5th ed.)

Georges S. Boolos, John P. Burgess and Richard C. Jeffrey

Cambridge University Press

Must have.

AroraBarak.jpg

Computational Complexity: A Modern Approach

Sanjeev Arora and Boaz Barak

Cambridge University Press

Must have.