Elements of the Theory of Computation

This book is an introduction, on the undergraduate level, to the classical and contemporary theor y of computation . The topics covered are, in a few words, the theory of automata and formal languages, computability by Turing machines and recursive functions, uncomputability, computationa l complexity, and mathematical logic . The treatment is mathematical but the viewpoint is that o f computer science ; thus the chapter on context-free languages includes a discussion of parsing, an d the chapters on logic establish the soundness and completeness of resolution theorem-proving .