The material in this book covers the topics suggested in the ACM curriculum guidelines for the Theory of Computation course, and in the Foundations of Computing course in the model liberal arts curriculum. This is one of the standard courses for upper-level computer science majors, and beginning graduate students.

The material in this area is intellectually deep, and students invariably find it highly challenging to master. This book blends three key ingredients to the successful mastery. First is its attention to the coalescing of intuition and rigor that is required to fully understand the area. This mingling is accomplished not only in the discussion and in examples, but also especially in the proofs. I believe that this is one of the keys to students achieving proficiency in this area. A number of practical applications are presented to illustrate the capacity of the theoretical techniques to contribute insights in a variety of areas. Such presentations greatly amplify the reader's motivation for the theoretical material, and motivation is a second necessary prerequisite to learning. The student's active participation is the third and final major element in the learning process, and to this end, an extensive collection of problems of widely differing difficulty is incorporated.

The book introduces new presentations of standard computational models that help avoid pitfalls of the conventional description methods. It also includes novel approaches to some of the topics that students normally find the most challenging. The presentation has evolved in response to student reactions over many years of teaching and is well received by students.