Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
cross-posted:… – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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