Rice-Shapiro Theorem

The Rice-Shapiro theorem is thus phrased (due to Mr. Zunino's notes, link ), Given $\mathcal{F}$ is a set of partial recursive functions, i.e. $\mathcal{F} \subseteq \mathcal{R}$. Also $A = \{ n | \varphi_n \in \mathcal{F} \} \in \mathcal{RE}$. Then $$ f \in \mathcal{F} \Leftrightarrow \exists g \subseteq f . \big( \mathsf{dom}(g) \textit{ is finite} \wedge g \in \mathcal{F} \big) $$ It is rewritten in the counter-positive manner to prove $A \notin \mathcal{RE}$.

• check $A$ is semantically closed
• ($\Rightarrow$) pick $f \in \mathcal{F}$ s.t. $\nexists g \subseteq f . g \in \mathcal{F} \wedge \mathsf{dom}(g) \textit{ is finite}$
• ($\Leftarrow$) pick $f \notin \mathcal{F}$ s.t. $\exists g \subseteq f . g \in \mathcal{F} \wedge \mathsf{dom}(g) \textit{ is finite}$

Some examples.

• $A = \{ n | \mathsf{dom} (\varphi_n) \backslash \mathsf{ran} (\varphi_n) \neq \varnothing \}$
• $B = \{ n | \mathsf{dom} (\varphi_n) \text{ is finite} \}$
• $C = \{ n | \mathsf{dom} (\varphi_n) \text{ is infinite} \}$

$A \notin \mathcal{RE}$. By R-S $\Leftarrow$, we provide $g(0)=1 \in \mathcal{F}$, also we scheme $f(0)=1,f(1)=0$, s.t. $g \subseteq f \wedge f \notin \mathcal{F}$, both $f$ and $g$ are finite (let the otherwise case undefined).

$B$ and $C$ are both not $\mathcal{RE}$ (directly from R-S theorem). This says, the set of indices of all finite domain functions are not recursively enumerable. So is the set of indices of all infinite domain ones.