The point of view of this book, which presents a broad introduction to the theory of computation, is very much that of recursion theory. Given that, however, the book’s treatment and content are fairly standard. In the preface, the author says that An introduction to the general theory of algorithms by Machtey and Young [1] going out of print was one of the main reasons he wrote this book. The purpose of the book is educational; the writing style is that of a polished course text. The author tries to illustrate and motivate the theoretical results and definitions using analogies with practical programming. The level of presentation is rigorously mathematical and to the point, yet at the same time highly intuitive. I found this the most remarkable feature of the text. Useful exercises appear throughout (rather than clustered at the end of each chapter), and many of them are solved in an appendix. Historical notes refer quite adequately to the core literature. A brief index is provided.

According to Smith, the material in this book can be covered in one semester. Chapter 1, “Models of Computation,” introduces random access machines, partial recursive functions, and Turing machines, and gives a complete and detailed proof of the equivalence between RAM-computable and partial recursive functions. Chapter 2, “Basic Recursive Function Theory,” emphasizes acceptable programming systems, recursion theorems, and index sets. I found this chapter to be didactically excellent. Chapter 3, “Abstract Complexity Theory,” discusses program size measures and restricted programming systems, in addition to the standard material on complexity gaps, compression, and speedup. Finally, chapter 4, “Complete Problems,” starts by briefly discussing complete sets for recursive enumerability, and then moves on to computational complexity theory, covering constant speedup and the time hierarchy theorem; deterministic space simulation of nondeterministic space; closure of space classes under complement; and basic NP-complete problems.