An Introduction to the Theory of Computation

Amazon.com

"Intended as an upper-level undergraduate or introductory graduate text in computer science theory," this book lucidly covers the key concepts and theorems of the theory of computation. The presentation is remarkably clear; for example, the "proof idea," which offers the reader an intuitive feel for how the proof was constructed, accompanies many of the theorems and a proof. Introduction to the Theory of Computation covers the usual topics for this type of text plus it features a solid section on complexity theory--including an entire chapter on space complexity. The final chapter introduces more advanced topics, such as the discussion of complexity classes associated with probabilistic algorithms./p>

Reviews From AMAZON.COM

Technical and Thorough at the Expense of Readability

This book, while generally pretty complete, seems to have trouble explaining the concepts in anything other than formal definitions and the few "user friendly" explanations that is does give leave quite a bit to be desired. This book would make a great reference for anyone already familiar with the concepts of computability but does little to accommodate readers that are new to the subject. There are some pretty good step by step explanations of more basic subjects like non-deterministic finite automata but the explanations that are given for more complicated topics are very flaky. Take the pumping lemma for example. The book gives a very brief overview, a more formal definition, and then (prematurely) jumps into examples. One key concept, "pumping length," is described simply as "a certain special value." Its meaning is vaguely hinted at on the next page but is never actually stated - formally or in plain English.

A Classic

Extremely well written. If you are a student you'll find it very easy to follow - particularly the proofs. Just buy it, i guarantee you will not be dissappointed.