Rice’s theorem and recursion theorem

374 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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.