This updated edition of Michael Sipser's successful handbook tells the captivating story of computation theory - a field that encompasses elegant conclusions and exciting unanswered questions at the intersection of mathematics and computer science.

Sipser's direct, clear style allows students at any level to understand and enjoy this field of study. The groundbreaking sections on proof ideas intuitively reveal the ideas that underlie formal proofs of theorems, explaining fundamental concepts in everyday language.

The new edition has been enhanced in various ways based on feedback from students and instructors over the years, and includes fully revised and classroom-tested problem sets, with representative solutions at the end of each chapter.