As I understand it Rice's Theorem seems to imply the existence of the Halting problem. That is, with Rice's Theorem, we can prove that the Halting problem is undecidable. However, to me, it seems like one could write a proof using that the Halting problem is undecidable to show Rice's Theorem. I'm not exactly sure how one would go about proving such a thing (though it seems by contradiction would be the natural thing to do), but it feels to me that that it should be possible?
2
-
1$\begingroup$ Sure. Yup, they are equivalent; you can prove either starting from the other. In some sense all statements that true are equivalent. Is that useful? Is that what you want to ask? $\endgroup$– D.W. ♦Commented Oct 15, 2020 at 21:10
-
1$\begingroup$ @D.W. "... true [and provable] are equivalent." Just being pedantic. $\endgroup$– plopCommented Oct 15, 2020 at 21:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, you can prove Rice's theorem by reduction from the Halting problem. See https://en.wikipedia.org/wiki/Rice%27s_theorem#Proof_by_reduction_from_the_halting_problem.
The reverse direction is also provable and is trivial.
In some sense all statements that true and provable are equivalent, in the sense that you can prove any by starting from any other, but that probably isn't a useful observation.
