Geodesic
Rice Theorems for ∑n -1 Sets
Canadian journal of mathematics, Tome 29 (1977) no. 4, pp. 794-805

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

In [3] Hay proves generalizations of Rice's Theorem and the Rice-Shapiro Theorem for differences of recursively enumerable sets (d.r.e. sets). The original Rice Theorem [5, p. 3G4, Corollary B] says that the index set of a class C of r.e. sets is recursive if and only if C is empty or C contains all r.e. sets. The Rice-Shapiro Theorem conjectured by Rice [5] and proved independently by McNaughton, Shapiro, and Myhill [4] says that the index set of a class C of r.e. sets is r.e. if and only if C is empty or C consists of all r.e. sets which extend some element of a canonically enumerable class of finite sets. Since a d.r.e. set is a difference of r.e. sets, a d.r.e. set has an index associated with it, namely, the pair of indices of the r.e. sets of which it is the difference. 
Johnson, Nancy. Rice Theorems for ∑n -1 Sets. Canadian journal of mathematics, Tome 29 (1977) no. 4, pp. 794-805. doi: 10.4153/CJM-1977-082-3
@article{10_4153_CJM_1977_082_3,
     author = {Johnson, Nancy},
     title = {Rice {Theorems} for \ensuremath{\sum}n -1 {Sets}},
     journal = {Canadian journal of mathematics},
     pages = {794--805},
     year = {1977},
     volume = {29},
     number = {4},
     doi = {10.4153/CJM-1977-082-3},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1977-082-3/}
}
TY  - JOUR
AU  - Johnson, Nancy
TI  - Rice Theorems for ∑n -1 Sets
JO  - Canadian journal of mathematics
PY  - 1977
SP  - 794
EP  - 805
VL  - 29
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1977-082-3/
DO  - 10.4153/CJM-1977-082-3
ID  - 10_4153_CJM_1977_082_3
ER  - 
%0 Journal Article
%A Johnson, Nancy
%T Rice Theorems for ∑n -1 Sets
%J Canadian journal of mathematics
%D 1977
%P 794-805
%V 29
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1977-082-3/
%R 10.4153/CJM-1977-082-3
%F 10_4153_CJM_1977_082_3

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

[2] 2. Hay, L., A discrete chain of degrees of index sets, J. Symb. Log. 37 (1972), 139–149. Google Scholar

[3] 3. Hay, L. Rice theorems for d.r.e. sets, Can. J. Math. 27 (1975), 352–365. Google Scholar

[4] 4. Myhill, J., A fixed point theorem in recursion theory, Abstract, J. Symb. Log. 20 (1955), 205. Google Scholar

[5] 5. Rice, H. G., Classes of recursively enumerable sets and their key arrays, Trans. Amer. Math. Soc. 74 (1953), 358–366. Google Scholar

[6] 6. Rogers, H., Jr., Computing degrees of unsolvability, Math. Annalen 138 (1959), 125–140. Google Scholar

Cité par Sources :