The Theory of Computation

More about the book

This modern introduction to the theory of computation takes a practical approach, emphasizing problem-solving through computation amid realistic resource constraints. It explores key questions and methods that define theoretical computer science while relating developments to practical computing issues. The text establishes clear limits to computation, connects these limits to resource usage, and examines avenues for compromise through approximation and randomization. It also surveys current research areas in theoretical computer science likely to impact computing practices in the near future. Highlights include motivating theoretical developments by linking them to practical issues, providing informal overviews to build intuition for each result and proof, and introducing models from finite automata to universal models, including recursion theory. The emphasis on complexity theory begins with a thorough discussion of resource use in computation. The book is rich with examples and uses diagrams to illustrate abstract concepts, presenting difficult recent results informally, highlighting their profound implications for computing. The writing is literate and careful, offering clear motivations and insightful reflections on the implications of the author's proofs, making it a refreshing contribution to theoretical computer science.