Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-19T18:25:36.720Z Has data issue: false hasContentIssue false
  • English
  • Français

Rice Theorems For D.R.E. Sets

Published online by Cambridge University Press:  20 November 2018

Louise Hay
Louise Hay*
Affiliation:
University of Illinois at Chicago Circle, Chicago, Illinois
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Two of the basic theorems in the classification of index sets of classes of recursively enumerable (r.e.) sets are the following:

(i) The index set of a class C of r.e. sets is recursive if and only if C is empty or contains all r.e. sets; and

(ii) the index set of a class C or r.e. sets is recursively enumerable if and only if C is empty or consists of all r.e. sets which extend some element of a canonically enumerable class of finite sets.

The first theorem is due to Rice [7, p. 364, Corollary B]. The second was conjectured by Rice [7, p. 361] and proved independently by McNaughton, Shapiro, and Myhill [6].

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 27 , Issue 2 , 01 April 1975 , pp. 352 - 365
Copyright
Copyright © Canadian Mathematical Society 1975

References

1. Cooper, S. B., Degrees of sets bounded-truth-table reducible to creative sets (to appear).Google Scholar
2. Ershov, Y. L., A hierarchy of index sets, I, Algebra and Logic 7 (1968), 25–43.Google Scholar
3. Hay, L., A discrete chain of degrees of index sets, J. Symbolic Logic 37 (1972), 139–149.Google Scholar
4. Hay, L., Index sets of finite classes of recursively enumerable sets, J. Symbolic Logic 34 (1969), 39–44.Google Scholar
5. Hay, L., Manaster, A. B., and Rosenstein, J. G., Small recursive well-orderings, many onedegrees and the arithmetical difference hierarchy (to appear in Ann. Math. Logic).Google Scholar
6. Myhill, J., A fixed point theorem in recursion theory, Abstract, J. Symbolic Logic 20 (1955), p. 205.Google Scholar
7. Rice, H. G., Class of recursively enumerable sets and their decision problems, Trans. Amer. Math. Soc. 74 (1953), 358–366.Google Scholar
8. Rice, H. G., On completely recursively enumerable classes and their key arrays, J. Symbolic Logic 21 (1956), 304–308.Google Scholar
9. Rogers, H., Jr., Theory of recursive functions and effective computability (McGraw-Hill, New York, 1967).Google Scholar