This book provides an introduction to the theory of computation. It is aimed primarily at undergraduate computer science students who are comfortable with mathematical notation, definitions and proofs, and especially with reading a detailed mathematical presentation. The author also intends his book to be useful to others in disciplines that depend in some way on the theory of computation.

The author provides a very detailed and very thorough treatment of the standard theory of computability and complexity. He says that his broadest goal is to confer an understanding of both the capabilities and the limitations of computation. The focus is on the questions of what is computable and what is efficiently computable. The approach to this is intrinsically mathematical. The book’s organization depends on a succession of computational models, which are viewed as mathematical descriptions of computing devices.

It begins with the theory of finite automata, first deterministic, then non-deterministic, followed by other variations. The subject is built up very carefully from the concepts of alphabets and languages with rigorous proofs and examples. (Indeed, the relationship between language classes and the computational models that define them is a major theme of the book.)

The discussion then turns to Turing machines, considerably more general and more powerful than automata, and the basis for much that follows. Computability theory is introduced to formalize the concept of an algorithm as a fully developed computational model. In particular, the halting deterministic Turing machine is used to formalize the intuitive idea of an algorithm. Computable languages then appear as the corresponding languages that this kind of Turing machines define. The model of computing with deterministic Turing machines makes it easy to impose bounds on time and space.

Much of the rest of the book (well more than half of the text) is devoted to complexity theory. This begins with a formalization of the concept of an efficient algorithm, and continues by studying the class of languages that admit efficient algorithms. Graph-theoretic tools become an important component. The first part studies time-bounded computation, and introduces polynomial-time deterministic computation and the framework of NP-completeness.

Toward the end of the book the author presents more advanced topics from complexity theory – space-bounded computation, hierarchy results (describing what more one can do with additional units of time and space resources), and then some parametrized complexity theory.

This is a very complete treatment of the standard subject. While it touches very briefly on parallel computation, other variations such as distributed computing are not directly addressed. Quantum computation is never mentioned.

Extensive sets of exercises and bibliographies are provided for each chapter.

Bill Satzer (bsatzer@gmail.com), now retired from 3M Company, spent most of his career as a mathematician working in industry on a variety of applications. He did his PhD work in dynamical systems and celestial mechanics.