Rice's theory description

I've lately read a write-up 'Theories of computational intricacy'. In the write-up it mentions that with Rice is theorem one can confirm that, as an example, $i∈[\mathbb N:\phi_i$ is a constant function , is not recursive, yet I can not see just how. I currently recognize the theory, yet I do not actually get just how I can utilize it. Thanks for your solution!

2019-12-02 02:54:22
Source Share
Answers: 1

Rice is theory claims that for any kind of part $F$ of the class $T$ of partial determinable functions, the set $\{i\mid \phi_i\in F\}$ is recursive iff $F=\emptyset$ or $F=T$.

Allow $F$ be the set of partial determinable functions that are constant on their domain name. $F$ is absolutely non - vacant, given that the function that constantly takes the value 0 is absolutely determinable. $F$ is additionally not the entire class $T$, given that the function $\phi$ with $\phi(0)=0$, $\phi(n)=1$ for $n>0$ is absolutely determinable and also not constant.

It adheres to that the set you want is not recursive.

If your complication hinges on just how to convert the common declaration of Rice is theory (in regards to choice troubles) right into the variation I created, merely bear in mind that officially a choice trouble is a set $D\subseteq{\mathbb N}$, and also the trouble is decidable iff $D$ is recursive. Certainly, this is generally mentioned by claiming that there is a Turing equipment that, offered $n$, determines whether $n\in D$ or otherwise. Yet this is absolutely the like claiming that the equipment calculates the particular function of $D$, which is (the definition of) being recursive.

2019-12-03 04:24:44