Soare, Robert I. 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 Cited in 3 ReviewsCited in 349 Documents 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 Keywords:r.e. sets; Post’s problem; oracle; finite injury priority method; infinite injury priority method; minimal pair method; r.e. degrees; lattice of r.e. sets; degree of information PDFBibTeX XML