# Rice’s theorem and recursion theorem

Prove Rice’s theorem using recursion theorem.

I need some hints as to what must be done about it. Please use Davis' book notation: Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science.

-
cross-posted: cs.stackexchange.com/questions/11947/… –  A.Schulz May 11 '13 at 8:14
I thought that was another question. The other one is deleted now, sorry everyone. –  Gigili May 11 '13 at 8:37
This is a relatively standard construction - basically any proof of Rice's theorem can be reworked into a proof that uses the recursion theorem. –  Carl Mummert May 15 '13 at 13:30
Hint: The recursion theorem says that if you have any program $P$ that transforms programs into programs (i.e. P(Q) is a program), there must be a program $Q$ such that $P(Q)$ behaves exactly like $Q$. From a failure of Rice's theorem, you can build a program that violates this.