This book is a survey of the theory of computability. It leads from the basics of ordinary recursion theory (with the role of Turing machines taken over by other machine models) to an introduction to several of the more recent research areas. The last third of the book is devoted to recursion theory on sets of cardinality of the continuum. For advanced readers it may very well serve as an introduction to the subject: they will appreciate the rigorous formalism, the clarity of presentation, and the informal discussions. For most undergraduate students, however, even the material of part 1 is generally known to be difficult, no matter how it is presented; unless they are thoroughly trained in mathematical notation, undergraduate computer science majors are likely to get lost within the extensive formalism of the chosen approach without grasping the subject. But, for that purpose, expositions based on concepts that do not require heavy formalism (e.g., classical Turing machines) are readily available in the literature. As indicated above, the use of precise formalism is a strength of the book, and an index to notations makes it suitable for reference. Plenty of exercises accompany the text.
The first 300 pages deal with ordinary recursion theory. A general, flowchart-based framework for various machine models is introduced in chapter 1.1. The concepts of syntax and semantics, substitutions (or subroutines), and similarity are rigorously worked out. The computability of functions N → N is characterized by register machines (chap. 1.2), while programs (chap. 1.4), and &mgr;-recursion (chap. 1.3). Functions on words W ( &Sgr; ) → W ( &Sgr; ) over some alphabet &Sgr; are considered separately and characterized by stack machines (chap. 1.7), which are register machines operating on strings, and by tape machines (chap. 1.5). Tape machines are essentially standard Turing machines as they appear in the framework established in chapter 1.1. The connection between number and word functions is drawn in chapter 1.7 via some numbering of W ( &Sgr; ), which is a modification of the commonly used number representation with respect to base | &Sgr; | . It might come as a surprise that the fundamental concept of syntax and semantics so rigorously dealt with at the machine level is not carried through all the way to the data level. The basic experience that any real machine operates on syntactical objects such as strings rather than on abstract number concepts also could have shifted the viewpoint by looking at word functions primarily as a syntactical vehicle to handle number functions. After all, Turing machines were originally invented to do numerical computations (semantics) rather than string manipulation (syntax). Generally, motivation and discussions are given in adequate detail. This is a considerable convenience to the reader and is not often provided in technical monographs. An exception to this is the presentation and discussion of Church’s thesis, which is somewhat meager for such a central point of basic computability theory. Along these lines, “reference to Church’s thesis” (p. 91) or what is commonly called “proof by Church’s thesis” is always to be understood as an intentional abuse of language rather than a merely inadequate reference. The rest of part 1 introduces the standard material of basic recursion theory: recursively enumerable sets, unsolvable problems, and Gödel numberings of the partial recursive number functions. A more complete coverage of Gödel numberings is given in chapters 2.2 and 2.3.
Given the book’s intention of presenting a modern account of computability theory, the axiomatic characterization of the class of partial recursive number functions based on the characterization of the standard numbering (Th. 1.9.10) by utm-theorem and smn-theorem would have been an attractive alternative to the rather short discussion of the extension of Church’s thesis on page 115.
Numberings are used to transfer the theory of computability from number functions to functions on other denumerable domains (chap. 2.2). Many-one and one-one reducibility of numberings are compared in chapter 2.4. The exposition of the general recursion theorem stated in terms of numberings follows Ershov [1]. It includes a generalization of Rice’s theorem and isomorphism theorems for numberings. Chapter 2.6 gives an elegant presentation of creative, productive, and complete sets. Chapter 2.7, on effective numberings, is an account of Reiser and Weihrauch [2] and takes a look at questions like the following: Given an n -ary operation h : S n → S what numberings of S make h a computable operation? A related question of particularly practical relevance would be to ask for the existence of numberings that feature efficient (i.e., low-complexity) algorithms for several operations simultaneously. Chapters 2.8-2.12 provide short introductions to several very important areas: computable ordinals, including a proof that an ordinal is computable if and only if it is recursive (2.8); applications to logic, in particular the Gödel-Rosser incompleteness theorem (2.9); relativized recursion theory, containing mainly definitions (2.10); Friedberg-Muchnik’s priority argument that incomparable recursively enumerable degrees do exist, and the arithmetical hierarchy (2.11); and abstract complexity theory: complexity classes and compression and speed-up theorems (2.12).
Part 3 of the book develops recursion theory on sets of cardinality of the continuum. Since there is no comprehensive presentation of Type 2 recursion theory in the literature, this may be the most interesting part of the book. In chapter 3.1, computability is considered for functions on subsets of natural numbers ( P &ohgr; ), on sequences of natural numbers (:G1o), and on 0–1 sequences ( &CC; 0 ). In each case a natural topology is given via approximation by finite elements, and a function is computable if an approximation of its graph by finite elements is recursively enumerable. A necessary condition for computability is continuity. The equivalence of the three computability models is established in a natural way by representations.
In ordinary recursion theory, the Gödel numbering of partial recursive number functions plays a fundamental role. Chapter 3.2 explores its analogies in the recursion theory on Baire’s space &BB;> of infinite sequences of natural numbers; representations of the continuous functions are introduced and characterized by analogs of the utm- and smn-theorems. Computably open subsets of &BB;> correspond to recursively enumerable sets in ordinary recursion theory, and analogs of noncomputability and undecidability are discussed. A theory of representations and effective representations is developed in order to transfer the concept of computability to other domains. The exposition follows Kreitz and Weihrauch [3].
One of the most fruitful concepts in Type 2 recursion theory may be that of complete partial orders (cpo). This model is introduced in chapter 3.5. The function space of continuous functions between cpo’s is characterized by analogs of utm- and smn-theorems, and a constructive version of the fixed-point theorem is proved. When studying computability by means of a representation &dgr; &BB; → M the standard Gödel numbering of partial recursive number functions automatically induces a numbering &ngr; of the &dgr;-computable elements of M . Now, under what conditions are the &ngr;-computable functions precisely the restrictions of the &dgr;-computable functions to the computable elements? The theorems of Ceitin, Kreisel, Lacombe, Shoenfield, and Moschovakis (for metric spaces) and Myhill and Shepherdson (for cpo’s) give partial answers and are presented in chapter 3.6. The construction of new cpo’s satisfying certain recursion equations is considered in chapter 3.7. Finally, as an application to analysis, the determination of zeros of continuous functions on real numbers provides an instructive example that is studied in some detail.
Overall, this book is a valuable contribution to the literature, particularly part 3 and individual sections of the two previous parts.
