Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Some theorems on classes of recursively enumerable sets


Authors: J. C. E. Dekker and J. Myhill
Journal: Trans. Amer. Math. Soc. 89 (1958), 25-59
MSC: Primary 02.00
MathSciNet review: 0097310
Full-text PDF Free Access

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [1] M. Davis, Computability and unsolvability, McGraw-Hill, New York, 1958. MR 0124208 (23:A1525)
  • [2] J. C. E. Dekker, The constructivity of maximal dual ideals in certain Boolean algebras, Pacific J. of Math. vol. 3 (1953) pp. 73-101. MR 0053910 (14:838e)
  • [3] -, Two notes on recursively enumerable sets, Proc. Amer. Math. Soc. vol. 4 (1953) pp. 495-501. MR 0058533 (15:385a)
  • [4] -, Productive sets, Trans. Amer. Math. Soc. vol. 78 (1955) pp. 129-149. MR 0067049 (16:663a)
  • [5] J. C. E. Dekker and J. Myhill, Recursion theory, to be published by the North Holland Pub. Co., Amsterdam.
  • [6] 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.
  • [7] S. C. Kleene, Introduction to metamathematics, New York, Van Nostrand, Amsterdam, North Holland Pub. Co., and Groningen, Noordhoff, 1952, x+550 pp. MR 0051790 (14:525m)
  • [8] S. C. Kleene and E. L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. vol. 59 (1954) pp. 379-407. MR 0061078 (15:772a)
  • [9] R. McNaughton, On the effective distinguishability of classes of theories, abstract, J. Symbolic Logic vol. 19 (1954) p. 157.
  • [10] A. Mostowski, On definable sets of positive integers, Fund. Math. vol. 34 (1947) pp. 81-112. MR 0021923 (9:129f)
  • [11] -, On a set of integers not definable by means of one quantifier predicates, Ann. Soc. Polon. Math. vol. 21 (1948) pp. 114-119. MR 0026622 (10:175w)
  • [12] 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.
  • [13] J. R. Myhill, Creative sets, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik vol. 1 (1955) pp. 97-108. MR 0071379 (17:118g)
  • [14] J. R. Myhill and J. C. Shepherdson, Effective operations on partial recursive functions, ibid. vol. 1 (1955) pp. 310-317. MR 0077475 (17:1039b)
  • [15] E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. vol. 50 (1944) pp. 284-316. MR 0010514 (6:29f)
  • [16] H. G. Rice, Classes of recursively enumerable sets and their decision problems, Trans. Amer. Soc. vol. 74 (1953) pp. 358-366. MR 0053041 (14:713c)
  • [17] -, On completely recursively enumerable classes and their key arrays, J. Symbolic Logic vol. 21 (1956) pp. 304-308. MR 0081243 (18:369e)
  • [18] N. Shapiro, Degrees of computability, Trans. Amer. Math. Soc. vol. 82 (1956) pp. 281-299. MR 0085187 (19:2d)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02.00

Retrieve articles in all journals with MSC: 02.00


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1958-0097310-7
PII: S 0002-9947(1958)0097310-7
Article copyright: © Copyright 1958 American Mathematical Society