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.

  • $\begingroup$ I think you are right, but can you describe for example halting problem ,as a RE set, by this theorem? I mean for halting problem I can not construct $\Gamma$... $\endgroup$ – Hossein Apr 13 '17 at 7:44
  • $\begingroup$ @Hossein It is not true that any RE set is equal to $R_\Gamma$ for some $\Gamma$. For the halting problem, though, you can do it. Take $\Gamma$ to be the set of functions which are defined on input $0$. Then $R_\Gamma$ is the set of descriptions of such functions, which is the set of descriptions (programs) which halt on input $0$. $\endgroup$ – 6005 Apr 13 '17 at 21:00
  • $\begingroup$ You can also see that the theorem holds for thtis $\Gamma$. We have that $f \in \Gamma$ if and only if $f(0)$ is defined, so equivalently, $f \in \Gamma$ if and only if the function just sending $0$ to $a$ is a subset of $f$ for some $a \in \mathbb{N}$. $\endgroup$ – 6005 Apr 13 '17 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.