Bulletin of the American Mathematical Society

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

Book Information

Author(s): 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

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:
Journal: Bull. Amer. Math. Soc. 18 (1988), 108-112.
DOI: 10.1090/S0273-0979-1988-15624-8
PII: S 0273-0979(1988)15624-8

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS