Models of Computation and Formal Languages
 Gregory Taylor

This book explains the TuringTest, Markov algorithms, NP-completeness, etc.  Not exactly light reading.
----
ISBN 0-195-10983-X, CategoryBook