Rice-Shapiro theorem
[2/0%]LaTeX
Problem 5.4.5 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.4 "Reducibility"
(Rice's theorem for r.e. index sets) For any finite set , we say (in any order) is a code of . Show that an index set is r.e. if and only if
-
and imply ;
-
implies that there exists such that is a finite subset of ; and
-
There exists an r.e. set that contains codes of all and only finite sets such that (i.e., for each such that is finite, contains at least one of its code, and for every and every such that .
?
Origin: Stated according to the original source
Problem 5.4.8 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.4 "Reducibility"
?
Origin: Stated according to the original source
(a)
Show that there exists an r.e. set such that is not r.e.
(b)
Show that if is an r.e. index set then is also r.e.
References
[DuKo01] Du D., Ko K. Problem Solving in Automata, Languages, and Complexity. John Wiley & Sons, 2001.