The Pillars of Computation Theory

The author’s intentions are clear from the very beginning: he wants to change the way computation theory is taught to undergraduates. He says, “The abstract branch of theoretical computer science that we shall call ‘computation theory’ typically appears in undergraduate academic curricula in a form that obscures both the mathematical concepts that are central to the various components of the theory and the relevance of the theory to the typical student.” Accordingly, he presents an approach that emphasizes the mathematical underpinnings of computation theory. He believes that a deep understanding of the “big mathematical ideas” and operational control over them are the best ways for the typical student to incorporate these ideas into practical use. The intended audience includes advanced undergraduates and beginning graduate students.

The pillars of computation theory are three, according to the author: the concepts of state, encoding and nondeterminism. State refers to a stable configuration of a system, something that “comprises the fragment of its history that allows it to behave correctly in the future.” Encoding is essentially a mapping of one computational problem into another that allows a solution in one to be translated to a solution in the other. Nondeterminism is a fundamental notion that explains the apparent computational difficulty of many important computational problems. Among other things, it incorporates the P vs. NP question and the theory of NP-completeness. The reader will struggle to find explicit definitions of these three pillars in the text; the author’s approach suggests that we will come to know them when we see them.

The organization of the book follows naturally from the three pillars approach. There is an introductory section with mathematical preliminaries that includes, for example, a discussion of formal languages as well as background on graphs and trees. The section of the book that focuses on state revolves around the Myhill-Nerode theorem that gives a rigorous characterization of the notion of state. This section also includes an extended discussion of finite state automata and their generalization as abstract online automata.

The treatment of encoding begins with a discussion of countability and uncountability, and then moves on to the meat of computability theory. Starting with representation of computational problems as formal languages, the author proceeds to the halting problem, reducibility and the concept of semidecidability.

Complexity theory is the focus of the section on nondeterminism. The discussion begins with nondeterministic automata and Turing machines, continues with descriptions of time and space complexity and then defines and explores the classes P and NP, NP-completeness and NP-hard problems.

This approach to computation theory has an elegance that is mathematically appealing. But that elegance comes with a pedagogical cost. The author’s treatment demands a level of mathematical maturity and comfort with abstraction that may be a significant challenge for the average student. A typical computer science student might not be able to make meaningful practical connections without a good deal of additional support from an instructor. For the rarer student whose interests run to theoretical computer science, this would be a challenging and attractive book.

The author provides a set of sample exercises at the end of the book. These are not clearly associated with specific sections in the text. While this is not a bad idea in principle, this is another feature likely to work much better with strong students. For more typical students there are no exercises directly tied to the immediate text and few anywhere that are more routine — the kind many students need to ground themselves in the subject.

Bill Satzer (wjsatzer@mmm.com) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.