Garey, Michael R., and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.
Hein, James L: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison-Wesley, 1979. One of the standard references in the field.
Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998. An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.
The Complexity Zoo: A huge list of complexity classes, as reference for experts.
Computability Logic: A theory of interactive computation. The main web source on this new subject.
