On reducibility by recursive functions

On reducibility by recursive functions
HTML articles powered by AMS MathViewer

Proc. Amer. Math. Soc. 15 (1964), 889-892

DOI: https://doi.org/10.1090/S0002-9939-1964-0179079-9

PDF | Request permission

References

J. C. E. Dekker, Two notes on recursively enumerable sets, Proc. Amer. Math. Soc. 4 (1953), 495–501. MR 58533, DOI 10.1090/S0002-9939-1953-0058533-7
J. C. E. Dekker and J. Myhill, Recursive equivalence types, Univ. California Publ. Math. 3 (1960), 67–213. MR 0117155
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
Richard M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309–316. MR 109125, DOI 10.2307/2964290
S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, DOI 10.2307/1969708
John Myhill, Recursive digraphs, splinters and cylinders, Math. Ann. 138 (1959), 211–218. MR 111684, DOI 10.1007/BF01342904
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
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto-London, 1967. MR 0224462

On the structure of recursively enumerable sets