Bulletin of the American Mathematical Society

MathSciNet review: 1567671
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.

Theodore Baker, John Gill, and Robert Solovay, Relativizations of the ${\cal P}=?{\cal N}{\cal P}$ question, SIAM J. Comput. 4 (1975), no. 4, 431–442. MR 395311, DOI 10.1137/0204037

Alonzo Church, A set of postulates for the foundation of logic, Ann. of Math. (2) 34 (1933), no. 4, 839–864. MR 1503136, DOI 10.2307/1968702

Richard M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944), Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236–238. MR 84474, DOI 10.1073/pnas.43.2.236

4.

S. C. Kleene, A theory of positive integers in formal logic, Amer. J. Math. 57 (1935), 153-173; 219-244.

Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790

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, DOI 10.1007/BFb0016275

Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9

Ju. V. Matijasevič, The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR 191 (1970), 279–282 (Russian). MR 0258744

A. A. Mučnik, 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 0081859

P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp, Izdat. Akad. Nauk SSSR, Moscow, 1955 (Russian). Trudy Mat. Inst. Steklov. no. 44. MR 0075197

Emil L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197–215. MR 7893, DOI 10.2307/2371809

Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1

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, DOI 10.1016/0001-8708(83)90004-X

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, DOI 10.1016/0001-8708(87)90062-4

Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462

Larry J. Stockmeyer, The polynomial-time hierarchy, Theoret. Comput. Sci. 3 (1976), no. 1, 1–22 (1977). MR 438810, DOI 10.1016/0304-3975(76)90061-X

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.

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 0395311

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.