I am trying to learn the Rice–Shapiro theorem on my own. Here is the theorem:

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$.

I will appreciate if anybody helps me to make the theorem crystal clear. I just want to know what it really means and how I can use it to say that a set is not r.e., for example the set Empty or TOT.

  • $\begingroup$ I'm not sure what you mean by "what it really means". $\endgroup$ – Yuval Filmus Dec 21 '16 at 8:17
  • 4
    $\begingroup$ What is $R_\Gamma$? $\endgroup$ – Andrej Bauer Dec 21 '16 at 8:38
  • $\begingroup$ @YuvalFilmus , for example in the Rice Theorem we say if there is a feature that divides the set N into 2 distinct set , it's index set can't be recursive.what this theory tries to say clearly or with an example? $\endgroup$ – NedaHn Dec 21 '16 at 8:38
  • $\begingroup$ How do you "learn" a theorem? Please formulate a meaningful question. $\endgroup$ – Raphael Apr 12 '17 at 19:13
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 12 '17 at 19:14

Rice-Shapiro greatly helps in proving that a set is not RE, for some sets of the form $R_\Gamma$.

E.g. take $A = \{ n \ |\ {\sf dom}(\phi_n) \mbox{ finite} \}$. We have $A=R_\Gamma$ with $\Gamma = \{ \phi_n | {\sf dom}(\phi_n) \mbox{ finite} \}$. If $A$ were RE, since e.g. the always undefined function belongs to $\Gamma$, then by Rice-Shapiro any recursive extension of that would be long to $\Gamma$ as well -- but this is false, since e.g. the identity function $\notin\Gamma$. Hence $A$ is not RE.

The above one is a typical use, where you reach a contradiction by extending a function inside $\Gamma$ to one recursive function outside.

We can also use it in the other direction: we reach a contradiction if we can take any function inside $\Gamma$ whose finite restrictions are all outside $\Gamma$. For instance, take $B = \{n \ |\ \forall k\in\mathbb{N}.\ \phi_n(2k)=5 \}$. Clearly $B=R_\Gamma$ with $\Gamma = \{\phi_n \ |\ \forall k\in\mathbb{N}.\ \phi_n(2k)=5 \}$. The function $f(x)=5$ is inside $\Gamma$, but any finite restriction of $f$ can not evaluate to $5$ on all even numbers, hence it must be found outside $\Gamma$. If $B$ were RE, by Rice-Shapiro one such restriction should instead be found inside $\Gamma$. We conclude that $B$ can not be RE.

I find Rice-Shapiro easier to use if I think about it as two separate results:

One is a monotonicity result, telling us that if $f \in \Gamma$ and $f \subseteq g$ with $g$ partial recursive, then $g \in \Gamma$. I.e. recursive extensions of functions in $\Gamma$ must belong to $\Gamma$ -- otherwise, $R_\Gamma$ is not RE.

The other is a compactness result. For any function in $\Gamma$, there must be a finite restriction of it inside $\Gamma$ -- otherwise, $R_\Gamma$ is not RE.

Many, many common examples of non-RE sets violate one of these two conditions, making it simple to prove they are not RE. For instance, consider $C = \{n\ |\ \phi_n(3)\neq 4 \land \phi_n(5)=2 \}$, where the notation $\phi_n(3)\neq 4$ is meant to be true when $\phi_n(3)$ is undefined. This immediately violates monotonicity, since I can always extend a (recursive) function which is undefined on $3$ so that it evaluates to $4$ on that point (and still get a recursive function). So $C$ is not RE.

  • $\begingroup$ thank you so much specially about the examples they were really helpful. $\endgroup$ – NedaHn Dec 21 '16 at 9:39
  • 1
    $\begingroup$ @chi concerning the monotonicity result, shouldn't it only apply to finite such $f$s? I.e. only recursive extensions of finite functions in Γ must belong to Γ? $\endgroup$ – Beleg Jan 1 '19 at 13:44
  • 1
    $\begingroup$ @Beleg A strict reading of the Rice-Shapiro statement indeed only applies to finite $f$s, but it's easy to extend monotonicity to infinite $f$s as well. Indeed, let $g$ be a recursive extension of any $f\in\Gamma$. By Rice-Shapiro (compactness), there is a finite restriction $h\in\Gamma$ of $f$. But then $g$ extends $h\in\Gamma$ which is finite, hence by R-S(monotonicity) $g\in\Gamma$. So, monotonicity always holds for any $f$, finite or not. (Yours is a great point, BTW. I recall I had exactly the same objection when I met general monotonicity) $\endgroup$ – chi Jan 1 '19 at 14:08

The theorem says that any observation made about computable functions can be done by testing the values of the functions at finitely many arguments. In particular, acecss to the source code does not give you the ability to make more observations than what you get by trying out what the function does.

  • $\begingroup$ An r.e. set is a set whose membership can be observed, i.e., a computer can tell that something is in the set (for instance the source code of a function), but it cannot necessarily tell that something isn't in the set. In the theorem, the r.e. set in question is the set of programs that encode functions from $\Gamma$. $\endgroup$ – Andrej Bauer Dec 21 '16 at 8:59
  • $\begingroup$ Nah, I no point in really clarifying I think. $\endgroup$ – Andrej Bauer Dec 21 '16 at 11:19

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.