This book is announced as being the first book in computability theory written at an undergraduate level. It contains an Introduction and six chapters.
The Introduction contains an informal explanation of the Turing Machine, as well as the formulation of Church’s thesis.
Chapter 1, Mathematical Prerequisites, gives basic mathematical notions, such as sets, relations, functions, strings, and graphs, as well as some of their properties. The book gives so-called “naive” set theory without any warning; it seems to me that some set-theoretic paradoxes would be to the point. There are a number of small gaps: for example, on p. 15, it is unclear how the set {0,1} is ordered; then, what does “lexicographic ordering” of words over the alphabet mean? Generally, I guess the chapter is rather clear, though brief.
Chapter 2, Turing Machines, gives a formal definition of the Turing Machine, examples of Turing-computable functions, and some variants of the Turing Machine (multitape Turing Machine, and so on). The chapter also contains a standard diagonal example of a noncomputable function.
Chapter 3, Solvability and Unsolvability, is devoted to an unsolvable problem: the Halting Problem. Using this result, the author proves the unsolvability of the Post Correspondence Problem. Other problems of that sort (e.g., Hilbert’s tenth problem) are formulated. Unfortunately, an exact formulation of Matijasevich’s result is absent here, although it gives another characterization of computability.
Chapter 4, Formal Languages, introduces the reader to the notions of the theory of formal languages. The notions of recursive and recursively enumerable languages are given via Turing Machines. This is followed by sections devoted to phrase-structure grammars, context-sensitive grammars, context-free grammars, and, finally, regular grammars. The chapter gives other descriptions of the languages generated by the grammars (i.e., push-down automata and finite automata), though with no proofs of equivalence.
Chapter 5, Recursive Functions, gives the definitions of primitive recursive functions and partial recursive ones. Kleene’s theorem establishes that partial recursive functions are, in fact, equivalent to TM-computable functions.
Chapter 6, Complexity Theory, includes small sections on the following topics: an informal introduction to complexity evaluations; P versus NP; NP-completeness; pseudo-polynomial algorithms; complementary problems; the polynomial hierarchy; and space complexity.
The Appendix contains a Pascal program to simulate the Turing Machine. All of the chapters contain examples testing the reader’s understanding.
Although the list of references is large, there are some regrettable gaps in citation in the text itself. Perhaps careful citation is not so necessary in a book of this sort (I guess it is not necessary at all). But, the reader may be a little confused when he or she reads, for example, that the well-known Kleene’s theorem (right-linear grammars are equivalent to finite automata) was established in Rayward-Smith’s work of 1983.
The scope of the book’s contents is a little narrow. To my mind, the student has got to see the open problems in the research field. In order to achieve success in solving problems, the student needs to gain better knowledge than that of passive teaching. Also, to my taste, the book should have contained some key results, such as Gödel’s incompleteness theorem (along with a short chapter on deductive systems), some structure theorems for grammars and recursive functions, and so on. At the same time, some topics are thought to be optional (e.g., phrase-structure grammars and context-sensitive grammars).
Nonetheless, the book gives a wide list of definitions and basic results in computability theory, forming a general idea of the theory itself and about its main branches. No doubt, the book can be used as a first stage in computer education, provided that the reader then returns to those topics.
