You are here

Computability Theory

Rebecca Weber
American Mathematical Society
Publication Date: 
Number of Pages: 
Student Mathematical Library 62
[Reviewed by
Mark Hunacek
, on

If you happened to use Google on the 23rd of June, you may have noticed a graphic at the top of the page showing a strip of paper divided into cells, into which were inserted symbols like 0 and 1. This graphic illustrated a Turing machine, named for Alan Turing, the tortured genius who was born on June 23 a hundred years ago and who died just a few weeks before his 42nd birthday from cyanide poisoning, either by accident or from suicide (opinions vary, although the official inquest concluded the latter). Turing machines are an important aspect of the mathematical subject of computability theory, and they, as well as a good deal more, are discussed in this interesting and very well-written book, which in less than 200 pages of text succeeds admirably in its goal of making this subject accessible to undergraduates without a great deal of mathematical background. Indeed, it is not even assumed that the reader has a semester-long course in mathematical logic under his or her belt, and the necessary parts of that discipline are summarized in the text itself.

The book begins on an excellent note with chapter 1, which, in lieu of a preface, provides suggestions for reading the book and acknowledgement of sources which influenced the author, but which also contains, in just a few pages, an enlightening overview of the subject of computability itself, discussing in intuitive terms what a computable function is and how the notion of computability arose historically. Chapter 2 is then provided as a review of basic principles of logic and set theory, with a suggestion by the author that it should probably be read as the need arises, save for the first few sections, which should be skimmed for notation and terminology. (Additional review material also appears in an Appendix.)

The mathematical development of computability theory begins in earnest in chapter 3, the first of five chapters that comprise the basic core of the text. Chapter 3 addresses various different characterizations of the concept of computability (Turing machines, primitive and partial recursive functions, the lambda calculus, etc.) and discusses the Church-Turing thesis (that every computable function is Turing-computable). Chapter 4 is largely concerned with noncomputability; Kleene’s Recursion Theorem is stated and proved and as an application Rice’s theorem (which is too technical to state here, but which essentially establishes the existence of a large number of subsets of the natural numbers whose characteristic function is noncomputable) is proved, modulo some details that are left as an exercise. Examples of noncomputable problems (the Halting problem, Hilbert’s 10th problem, the word problem for semi-Thue systems, and the Post Correspondence Problem) are discussed.

In chapter 5, the notion of computability is extended from functions to sets (in a very natural way: a subset of the natural numbers is computable if its characteristic function is). The concept of computably enumerable (aka recursively enumerable) sets is also introduced and the distinction between these concepts explained. As an example of the author’s skill at explaining the intuition behind technical concepts, consider her brief but illuminating explanation of why a computably enumerable set need not be computable:

What’s the difference? Intuitively speaking, it’s the waiting. If A is being enumerated and we have not yet seen 5, we do not know if that is because 5 is not an element of A or because it’s going to be enumerated later.

Another nice feature of this chapter is a section giving an overview of the completeness and incompleteness theorems of Gödel and explaining the relationship between incompleteness and the existence of noncomputable sets.

Chapter 6 talks about the idea of relative computability and introduces concepts such as Turing reduction (technically defined in terms of something called “oracle machines,” the basic idea being that set A is reducible to set B if knowing B makes A computable) and finite injury priority arguments. Chapter 7 makes connections with first-order logic by talking about hierarchies of sets, including the arithmetical hierarchy (which involves the complexity of formulas that define sets).

Chapter 3 through 7, as previously noted, constitute the core of the book. Two chapters remain: the first is a “topics” chapter covering additional material, such as the limit lemma and Arslanov Completeness Criterion. (All of this was completely foreign to me).

The final and longest chapter in the book is an expository chapter that surveys some current research issues. Topics in this chapter include things like randomness, reverse mathematics and computable model theory. Each section of this chapter introduces an idea, gives some background results (sometimes without proof), and provides references (mostly to papers or lecture notes rather than textbooks). Having a lengthy chapter on current research in a book directed to undergraduates is perhaps a bit unusual, but I think it is an interesting idea to let students know what the current hot issues in a subject are, even if they are not yet ready to do research in the area themselves.

Of course, given the nature of the book and its intended audience, it cannot be, and certainly does not purport to be, an encyclopedic reference. Professionals in the field will surely notice certain topics that are not covered. Polynomial-time complexity and “P vs NP”, for example, are not covered here, though they are in Enderton’s book (cited below). Hilbert’s 10th problem is mentioned, but the proof is not discussed. I mention these examples only because they are among the few things in this area that I had heard about before getting this book. In fact, when the book first arrived I looked in the index to see what it did with Hilbert’s 10th problem, and could find no reference to it at all: no mention under Hilbert, Problem, Tenth, Robinson, Davis, or Matiyasevich. Then I started reading the book and discovered it mentioned as early as page 4. So, my one real criticism of the book is an index that could perhaps be improved.

Several competing textbooks that are roughly comparable in terms of length, content, and level of difficulty are Bridges’ Computability: A Mathematical Sketchbook, Enderton’s Computability Theory: An Introduction to Recursion Theory, Cutland’s Computability: An Introduction to Recursive Function Theory and Shen and Vereshchagin’s Computable Functions. I am admittedly not very familiar with any of these books, but from a quick perusal it appeared to me that (with the possible exception of Cutland’s book, which is now more than thirty years old, and which does not discuss all the topics that are covered in the book under review, such as the arithmetical hierarchy) Weber’s book is somewhat more chatty and accessible to undergraduates than they are. One noteworthy distinction between this text and Bridges’ is that roughly a third of the latter is devoted to solutions of the exercises, whereas Weber provides no solutions to the problems in her book, which are interspersed throughout the body of the text. (Since I believe that easy access to solutions is pedagogically inadvisable, I view this distinction as favoring Weber’s book for use as a class text, but the solutions may perhaps be helpful for somebody trying to use the book for self-study.)

It has always seemed to me that the main difficulty with learning this area of mathematics is that the underlying ideas can easily get lost behind a maze of technical details and difficult notation. Weber’s book cannot dispense with this completely; no intellectually honest account of the subject can. However, it seems to me that she has taken considerable care to minimize these inherent pedagogical problems. The intuition behind the details is generally spelled out, and the details themselves are sometimes deliberately downplayed.

As an example, the author provides a very nice intuitive explanation for why Ackermann’s function is not recursive; Bridges, by contrast, simply notes that this fact can be “shown by an involved argument” and provides a reference. Of course, not everybody likes intuitive plausibility arguments, and some teachers of a course in this area might prefer to see gory details; my view is that occasional reliance on intuition rather than technicalities (as long as nobody is being misled, which is the case here) is entirely appropriate for a book in this subject at this level.

As a result of good, clear writing, appeal to intuition when appropriate, and careful attention to the needs of a student-reader, Weber’s book, although certainly one that requires careful attention when reading, seems to be as accessible to undergraduates as is reasonably possible; anybody contemplating teaching a course in this subject will certainly want to carefully examine it, as will any student in such a course who, even if using a different textbook, wants a supplemental source of information. The book should also prove valuable to people wanting to learn this material by self-study.

Mark Hunacek ( teaches mathematics at Iowa State University.