1
$\begingroup$

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?

$\endgroup$
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.
    Oct 15 '20 at 21:10
  • 1
    $\begingroup$ @D.W. "... true [and provable] are equivalent." Just being pedantic. $\endgroup$
    – plop
    Oct 15 '20 at 21:18
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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