Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Rice-Shapiro theorem is:
Let $Γ$ be a set of computable functions such that the set $R_Γ$ is recursively enumerable. We have $f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.
If $Γ$ is singleton set, for example $Γ = \lbrace ϕ_{10}\rbrace$ then $R_Γ = \lbrace 10 \rbrace$ and is recursively enumerable, but $Γ$ does not satisfy:
$f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.
Where I have made a mistake?
The flaw is that $R_\Gamma$ includes not just the natural number $10$, but any natural number which gives rise to the same partial recursive function. It will be infinite, and not recursively enumerable.
In general, for any partial recursive function $f$ you can think of, there will be many Godel numbers which describe it. In other words, many partial recursive function descriptions result in the same actual function. If you are more familiar with Turing machines, there will always be many different Turing machines which compute the same abstract function or language.
In summary: $\Gamma$ is any set of functions. However, $R_\Gamma$ is the set of natural numbers which encode that function. In your case, for $\Gamma = \{\phi_{10}\}$, $R_\Gamma$ is the set of natural numbers which encode the same function as $10$, and this set is not recursively enumerable.
