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. A. Church, A set of postulates for the foundation of logic (second paper), Ann. of Math. (2) 34 (1933), 839-864. MR 1503136
  • 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. A. Kučera, An alternative, priority-free, solution to Post's problem, Lecture Notes in Computer Science (J. Gruska, B. Rovan and J. Wiederman, eds. ), No. 233, Springer-Verlag, Berlin and New York, 1986, pp. 493-500. MR 874627
  • 7. M. Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1983. 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. M. B. Pour-El and I. Richards, Noncomputability in analysis and physics: A complete determination of the class of noncomputable linear operators, Adv. in Math. 48 (1983), 44-74. MR 697614
  • 14. M. B. Pour-El and I. Richards, The eigenvalues of an effectively determined self-adjoint operator are computable, but the sequence of eigenvalues is not, Adv. in Math. 63 (1987), 1-41. MR 871080
  • 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