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