Geodesic
Rice Theorems For D.R.E. Sets
Canadian journal of mathematics, Tome 27 (1975) no. 2, pp. 352-365

Voir la notice de l'article provenant de la source Cambridge University Press

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]. 
Hay, Louise. Rice Theorems For D.R.E. Sets. Canadian journal of mathematics, Tome 27 (1975) no. 2, pp. 352-365. doi: 10.4153/CJM-1975-043-4
@article{10_4153_CJM_1975_043_4,
     author = {Hay, Louise},
     title = {Rice {Theorems} {For} {D.R.E.} {Sets}},
     journal = {Canadian journal of mathematics},
     pages = {352--365},
     year = {1975},
     volume = {27},
     number = {2},
     doi = {10.4153/CJM-1975-043-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1975-043-4/}
}
TY  - JOUR
AU  - Hay, Louise
TI  - Rice Theorems For D.R.E. Sets
JO  - Canadian journal of mathematics
PY  - 1975
SP  - 352
EP  - 365
VL  - 27
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1975-043-4/
DO  - 10.4153/CJM-1975-043-4
ID  - 10_4153_CJM_1975_043_4
ER  - 
%0 Journal Article
%A Hay, Louise
%T Rice Theorems For D.R.E. Sets
%J Canadian journal of mathematics
%D 1975
%P 352-365
%V 27
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1975-043-4/
%R 10.4153/CJM-1975-043-4
%F 10_4153_CJM_1975_043_4

[1] 1. Cooper, S. B., Degrees of sets bounded-truth-table reducible to creative sets (to appear). Google Scholar

[2] 2. Ershov, Y. L., A hierarchy of index sets, I, Algebra and Logic 7 (1968), 25–43. Google Scholar

[3] 3. Hay, L., A discrete chain of degrees of index sets, J. Symbolic Logic 37 (1972), 139–149. Google Scholar

[4] 4. Hay, L., Index sets of finite classes of recursively enumerable sets, J. Symbolic Logic 34 (1969), 39–44. Google Scholar

[5] 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] 6. Myhill, J., A fixed point theorem in recursion theory, Abstract, J. Symbolic Logic 20 (1955), p. 205. Google Scholar

[7] 7. Rice, H. G., Class of recursively enumerable sets and their decision problems, Trans. Amer. Math. Soc. 74 (1953), 358–366. Google Scholar

[8] 8. Rice, H. G., On completely recursively enumerable classes and their key arrays, J. Symbolic Logic 21 (1956), 304–308. Google Scholar

[9] 9. Rogers, H., Jr., Theory of recursive functions and effective computability (McGraw-Hill, New York, 1967). Google Scholar

Cité par Sources :