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.
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.
Copyright © 2021 JogjaFile Inc.
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.