Rice-Shapiro theorem

[2/0%]
LaTeX

(Rice's theorem for r.e. index sets) For any finite set D={x1,…,xn}D=\left\{ x_{1}, \ldots , x_{n}\right\}, we say [x1,…,xn]\left[x_{1}, \ldots , x_{n}\right] (in any order) is a code of DD. Show that an index set AA is r.e. if and only if

  1. x∈Ax \in A and Wx⊆WyW_{x} \subseteq W_{y} imply y∈Ay \in A;

  2. x∈Ax \in A implies that there exists y∈Ay \in A such that WyW_{y} is a finite subset of WxW_{x}; and

  3. There exists an r.e. set BB that contains codes of all and only finite sets WxW_{x} such that x∈Ax \in A (i.e., for each x∈Ax \in A such that WxW_{x} is finite, BB contains at least one of its code, and for every [x1,…,xn]∈B\left[x_{1}, \ldots , x_{n}\right] \in B and every xx such that Wx={x1,…,xn},x∈A)\left.W_{x}=\left\{ x_{1}, \ldots , x_{n}\right\} , x \in A\right).

?
?
(a)

Show that there exists an r.e. set BB such that ⋂n∈BWn\bigcap_{n \in B} W_{n} is not r.e.

(b)

Show that if BB is an r.e. index set then ⋂n∈BWn\bigcap_{n \in B} W_{n} is also r.e.

References

[DuKo01] Du D., Ko K. Problem Solving in Automata, Languages, and Complexity. John Wiley & Sons, 2001.