I've recently read a article 'Theories of computational complexity'. In the article it states that with Rice's theorem one can prove that, for example, {$i∈[\mathbb N:\phi_i$ is a constant function}, is not recursive, but I can't see how. I already know the theorem, but I don't really get how I can use it. Thank you for your answer!
Rice’s theorem explanation
1 Answers
Rice's theorem says that for any subset $F$ of the class $T$ of partial computable functions, the set $\{i\mid \phi_i\in F\}$ is recursive iff $F=\emptyset$ or $F=T$.
Let $F$ be the set of partial computable functions that are constant on their domain. $F$ is certainly non-empty, since the function that always takes the value 0 is certainly computable. $F$ is also not the whole class $T$, since the function $\phi$ with $\phi(0)=0$, $\phi(n)=1$ for $n>0$ is certainly computable and not constant.
It follows that the set you are interested in is not recursive.
If your confusion lies in how to translate the usual statement of Rice's theorem (in terms of decision problems) into the version I wrote, simply remember that formally a decision problem is a set $D\subseteq{\mathbb N}$, and the problem is decidable iff $D$ is recursive. Of course, this is usually stated by saying that there is a Turing machine that, given $n$, decides whether $n\in D$ or not. But this is certainly the same as saying that the machine computes the characteristic function of $D$, which is (the definition of) being recursive.
-
0thank you for the explanation! I understand it now. :) – 2010-11-28