A Recursive Introduction to the Theory of Computation, by Carl Smith, (Graduate Texts in Computer Science). Springer-Verlag, Berlin-New York-London, 1994, 148pp, US$29.95. ISBN 3-540-94332-3.
There is now some general agreement as to what constitutes a reasonable "theory of computation" course. Assuming that it follows one where the students have already met automata, the course should include at least the following.
* A section on models of computation.
* A section on basic recursion theory.
* A section on basic abstract complexity theory. (Though some would disagree with this.)
* A section on NP-hardness.
The section on models of computation introduces the student to several differing models of computation with a view towards establishing Church's Thesis and, more subtly (and implicitly), the idea of a reduction and Church's Polynomial Time Superthesis. Once this fairly messy section is dealt with, one can easily proceed to results like the existence of a universal machine, the undecidability of the halting problem, Rice's Theorem, the recursion theorems recursively enumerable sets, and possibly the arithmetic hierarchy. It is then natural to turn to abstract complexity theory, beginning with Blum's axioms which analyse the question "what is a complexity measure?", and then the speedup, gap, and compression theorems. One then can prove the classical hierarchy and tradeoff theorems. Finally, one turns to the last item above and works through Cook's Theorem into various concrete NP-completeness results.
This text grew from Carl Smith's Lecture notes from a one semester University of Maryland Computer Science Department course based around the classic out-of-print text "An Introduction to the Theory of Algorithms" by Machtey and Young. It follows the story outlined above more-or-less exactly. It has maintained the mathematical integrity of Machtey and Young's text, while addressing a number of comments to today's students such as comments regarding C++ and UNIX. I would regard the text as perfectly acceptable for either an honours course in computer science or in mathematics. The proofs are clean, efficient, and there seem very few typos. There are a large number of exercises of varying levels of difficulty, as well as solutions to some of the more challenging ones.
Of course, one always has a couple of gripes. First, a couple of the concepts seem to be used before they are defined and some are difficult to place via the index. For instance recursive enumerability is used in an exercise on pages 35 and 36 and yet is not defined until page 59 and the notion of a recursive set is defined on page 54, and used synonymously with decidable set (although this is neither in the index nor explicitly mentioned), yet the index refers the reader to page 59. Personally, I do not like the diagrams that the author uses to diagrammatically represent various internally defined functions. I found them at worst confusing, and at best unhelpful. (Perhaps they are aimed at "real" computer scientists.) I would have liked to have seen some other topics included, such as an application of the halting problem to a concrete problem such as Post Correspondence Systems, or Word problems in Semigroups. I would like to have seen mention of the arithmetical hierarchy, Turing reducibility, and the jump operator. (Here I am sure that the computer science audience at Maryland has affected treatment.) Personally, I always include Post's Problem and the priority method. Finally, I believe that some of the more recent results in structural complexity might be included such as those on inductive counting or interactive protocols.
The text competes with an increasing number of texts such as those of, Lewis and Papadimitriou, Salomaa, and Douglas Bridges. Aside form the few quibbles above, I believe that it does so very well. The only real prerequisite is "mathematical maturity". (In a computer science department, one would assume that students would have met automata and some analysis of algorithms.) Modest yet precise in scope, and very readable, I believe it to be an excellent choice as a text for any advanced first course in the theory of computation. I will certainly have no hesitation in using it in the future in my own course here at Victoria.