Michael Sipser.
Introduction to the Theory of Computation.
PWS Publishing. 1997
(read but not reviewed)
This book—by a noted authority and educator in the field—presents
computer science theory from a uniquely intuitive, “big picture” perspective.
The author grounds his clear and interesting study on broad mathematical principles,
not low-level technical details:
proofs are presented with a “proof idea” component that reveals
the concept underlying the mathematical formalism.
Similarly, algorithms are presented using prose rather than pseudocode
to focus attention on the algorithms themselves, rather than on specific models.
Formerly published in a Preliminary Edition,
this First Edition features additional chapters on space complexity (Chapter 8),
provable intractability (Chapter 9)
and advanced topics in computability theory (Chapter 10).
For further information, see the World Wide Web site for the book at:
https://math.mit.edu/~sipser/book.html