The two most widely used text books on computability and complexity theory are:
Michael Sipser: Introduction to the Theory of Computation, 2/e, Cengage, 2005.
John E Hopcroft; Jeffrey D Ullman: Introduction to Automata Theory, Languages and, Computation, Addison-Wesley, 1979.
There is also a beautiful philosophy monograph for lay-people that works through the technical details of computability theory without the formal proofs.
Douglas Hoftstadter: Gödel, Escher, Bach, Basic Books, 1979.
Finally, the best introduction to computability may be a puzzle book by a famous logician:
Raymond Smullyan: The Lady or the Tiger and Other Logic Puzzles, Penguin, 1983. (Now in an inexpensive Dover edition, 2009.)
(He starts with a bunch of puzzles based on the Liar's paradox, and then works you through the construction of a self-referential statement in the guise of a Sherlock Holmes-style puzzle about a mysterious locked box.)
