Introduction to the Theory of Computation

Discusses such topics as: regular languages; context-free languages; Church-Turing thesis; decidability; reducibility; the recursion theorem; time complexity; space complexity; and provable intractability.