Classical recursion theory. The theory of functions and sets of natural numbers (Q1188502)

The book is the first volume of an impressive presentation of classical recursion theory whose aim is to introduce the fundamental notions and methods (classical means that the study is focused on (partial) functions over the naturals, and that notions, results or techniques from generalized recursion theory are used only in case they are relevant to the original setting). More sophisticated topics (namely, an abstract study of complexity of computation, a deeper study of r.e. sets, an analysis of limit sets as well as more connections between recursion theory and computer science, number theory, algebra, analysis and set theory) will be treated in the forthcoming two volumes. The basic methods used in this book are hierarchies (i.e. a stratification built from below) and degrees (equivalence classes). The book is divided into six chapters. In Chapter 1 the author defines the concept of recursive function: many different approaches lead to the same class of functions. Two fundamental generalizations of recursive functions, i.e. partial recursive functions and functionals are studied in Chapter 2, whereas r.e. sets form the subject of the next chapter. Hierarchies are introduced in Chapter 4; they start with the r.e. sets as primitives. The author studies the arithmetical, the analytical, the set- theoretical and the constructible hierarchies. The last two chapters are devoted to degrees: Turing degrees in Chapter 5, many-one and other degrees in Chapter 6. The Baire Category Theorem is a basic tool of proof. Starred sections and subsections deal with topics thought quite away from the immediate concern; they emphasize the vast connections between the basic theory and other branches of mathematics, computer science, physics or philosophy. These parts represent some of the main contributions of the author. Author's option is for breadth rather than depth; rudiments of many branches are presented, rather than complete and detailed expositions of a small number of topics. The style is informal, devoid of technicalities, and the chapters are self-contained to an unexpected degree. Another merit of the author is his constant attention to assign authorship to basic results and to supply reference information for further reading; his bibliographical list is monumental and up-to-date. Many classical topics are treated in original, simpler ways, with illuminating comments. As the author mentions himself, the book has been written to be both an adequate textbook and a reference manual. The dilemma of these quite irreconcilable goals was almost solved by offering a detailed treatment of the main problems and sketches for exercises and starred parts. The result is primarily an excellent reference manual which is highly recommended to everyone interested in recursion theory.