Some theorems on classes of recursively enumerable sets
HTML articles powered by AMS MathViewer
- by J. C. E. Dekker and J. Myhill
- Trans. Amer. Math. Soc. 89 (1958), 25-59
- DOI: https://doi.org/10.1090/S0002-9947-1958-0097310-7
- PDF | Request permission
References
- Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR 0124208
- J. C. E. Dekker, The constructivity of maximal dual ideals in certain Boolean algebras, Pacific J. Math. 3 (1953), 73–101. MR 53910
- 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, Productive sets, Trans. Amer. Math. Soc. 78 (1955), 129–149. MR 67049, DOI 10.1090/S0002-9947-1955-0067049-X J. C. E. Dekker and J. Myhill, Recursion theory, to be published by the North Holland Pub. Co., Amsterdam. R. M. Friedberg, The solution of Post’s problem by the construction of two recursively enumerable sets of incomparable degree of unsolvability, Bull. Amer. Math. Soc. Abstract 62-3-362.
- Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- 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 R. McNaughton, On the effective distinguishability of classes of theories, abstract, J. Symbolic Logic vol. 19 (1954) p. 157.
- Andrzej Mostowski, On definable sets of positive integers, Fund. Math. 34 (1947), 81–112. MR 21923, DOI 10.4064/fm-34-1-81-112
- Andrzej Mostowski, On a set of integers not definable by means of one-quantifier predicates, Ann. Soc. Polon. Math. 21 (1948), 114–119. MR 0026622 A. A. Muchnik, Negative answer to the problem of reducibility of the theory of algorithms, C. R. (Doklady) Acad. Sci. URSS vol. 108 (1956) pp. 194-197.
- John Myhill, Creative sets, Z. Math. Logik Grundlagen Math. 1 (1955), 97–108. MR 71379, DOI 10.1002/malq.19550010205
- J. Myhill and J. C. Shepherdson, Effective operations on partial recursive functions, Z. Math. Logik Grundlagen Math. 1 (1955), 310–317. MR 77475, DOI 10.1002/malq.19550010407
- 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
- H. G. Rice, Classes of recursively enumerable sets and their decision problems, Trans. Amer. Math. Soc. 74 (1953), 358–366. MR 53041, DOI 10.1090/S0002-9947-1953-0053041-6
- H. G. Rice, On completely recursively enumerable classes and their key arrays, J. Symbolic Logic 21 (1956), 304–308. MR 81243, DOI 10.2307/2269105
- Norman Shapiro, Degrees of computability, Trans. Amer. Math. Soc. 82 (1956), 281–299. MR 85187, DOI 10.1090/S0002-9947-1956-0085187-3
Bibliographic Information
- © Copyright 1958 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 89 (1958), 25-59
- MSC: Primary 02.00
- DOI: https://doi.org/10.1090/S0002-9947-1958-0097310-7
- MathSciNet review: 0097310