×

Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. (English) Zbl 0667.03030

Perspectives in Mathematical Logic. Berlin etc.: Springer-Verlag. xviii, 437 p. DM 68.00 (1987).
The book presents a comprehensive report over the last forty years on the programs, ideas and hopes expressed in the famous Post’s address to the AMS (1944). It is divided into four parts. Part A covers the period 1931- 43 and contains a concise presentation of basic recursion theory. In Part B one really begins the study of r.e. sets, Post’s problem, Friedberg and Muchnik solutions, oracle constructions and finite injury priority method. Part C, covering the period 1961-87, is directed toward the infinite injury priority method and the minimal pair method for studying the r.e. degrees and the lattice of r.e. sets (under inclusion). Special attention is paid to the analysis of the degree of information a r.e. set encodes. The last part is devoted to more advanced topics concerning the r.e. degrees and the lattice of r.e. sets.
The style adopted by the author is informal, but with full mathematical rigor. The emphasis on modular approach, on intuition and pictures helps the understanding of quite complicated constructions and points out the beauty and elegance of the theory. A careful examination of the monograph not only reveals the strong mathematical power of the author (who has been an active researcher in the field for over twenty years), but also his skill to attract and enjoy. Every mathematician with interest in computability should consult this book.
Reviewer: C.Calude

MSC:

03D25 Recursively (computably) enumerable sets and degrees
03-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03-03 History of mathematical logic and foundations
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
01A60 History of mathematics in the 20th century
01A65 Development of contemporary mathematics