Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

Book Review

The AMS does not provide abstracts of book reviews. You may download the entire review from the links below.


Full text of review: PDF   This review is available free of charge.
Book Information:

Author: Robert I. Soare
Title: Recursively enumerable sets and degrees: A study of computable functions and computably generated sets
Additional book information: Perspectives in Mathematical Logic, Springer-Verlag, Berlin, Heidelberg, New York, 1987, xviii + 437 pp., $35.00. ISBN 3-540-15299-7.

References [Enhancements On Off] (What's this?)

  • 1. T. Baker, J. Gill, and R. Solovay, Relativizations of the ${\cal P}=?{\cal N}{\cal P}$ question, Siam J. Comput. 4 (1975), 431-442. MR 395311
  • 2. Alonzo Church, A set of postulates for the foundation of logic, Ann. of Math. (2) 34 (1933), no. 4, 839–864. MR 1503136, https://doi.org/10.2307/1968702
  • 3. R. M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236-238. MR 84474
  • 4. S. C. Kleene, A theory of positive integers in formal logic, Amer. J. Math. 57 (1935), 153-173; 219-244.
  • 5. S. C. Kleene, Introduction to metamathematics, van Nostrand, New York, 1952. MR 51790
  • 6. Antonín Kučera, An alternative, priority-free, solution to Post’s problem, Mathematical foundations of computer science, 1986 (Bratislava, 1986) Lecture Notes in Comput. Sci., vol. 233, Springer, Berlin, 1986, pp. 493–500. MR 874627, https://doi.org/10.1007/BFb0016275
  • 7. Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718
  • 8. Ju. V. Matijasevič, Enumerable sets are diophantine, Dokl. Akad. Nauk. SSSR, N. S. 191 (1970), 279-282; English transl. in Soviet Math. Dokl. 11 (1970), 354-357. MR 258744
  • 9. A. A. Muchnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR N. S. 108 (1956), 194-197. (Russian) MR 81859
  • 10. P. S. Novikov, On the algorithmic unsolvability of the word problem in group theory, Trudy Mat. Inst. Steklov. 44 (1955). (Russian) MR 75197
  • 11. E. L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197-215. MR 7893
  • 12. E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284-316. MR 10514
  • 13. Marian Boykan Pour-El and Ian Richards, Noncomputability in analysis and physics: a complete determination of the class of noncomputable linear operators, Adv. in Math. 48 (1983), no. 1, 44–74. MR 697614, https://doi.org/10.1016/0001-8708(83)90004-X
  • 14. Marian Boykan Pour-El and Ian Richards, The eigenvalues of an effectively determined selfadjoint operator are computable, but the sequence of eigenvalues is not, Adv. in Math. 63 (1987), no. 1, 1–41. MR 871080, https://doi.org/10.1016/0001-8708(87)90062-4
  • 15. H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 224462
  • 16. L. J. Stockmeyer, The polynomial-time hierarchy, Theoret. Comput. Sci. 3 (1977), 1-22. MR 438810
  • 17. A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math; Soc. 42 (1936), 230-265; A correction, ibid. 43 (1937), 544-546.

Review Information:

Reviewer: Marian Boykan Pour-El
Journal: Bull. Amer. Math. Soc. 18 (1988), 108-112
DOI: https://doi.org/10.1090/S0273-0979-1988-15624-8
American Mathematical Society