1
$\begingroup$

Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed:

  • We want to reduce Rice's Theorem (decide if a language has the nontrivial property P) to the Halting Problem
  • We want to say "if the Halting Problem can be solved, then we can decide if a language as nontrivial property P"

Here's how I thought the proof might go:

  • Suppose we have a machine H that solves the halting problem. We want to use this machine to decide if a language has property P.
  • We construct a machine that uses H to decide a language has property P.

Example: Take P to be "language contains the string 1".

We want to use H to decide if the language of a TM M contains the string 1, i.e that the TM halts and accepts when given input 1.

Now, if M halts on 1, that doesn't mean it accepts 1, so we don't know if L(M) contains 1. On the other hand if M does not halt on 1, that certainly means that L(M) does not contain 1.

And that's where I'm stuck. Is it actually possible to use Rice's theorem to prove that the halting problem is undecidable?

$\endgroup$
  • $\begingroup$ You need to read this, I think. $\endgroup$ – Raphael May 28 '16 at 1:23
  • $\begingroup$ "Rice's Theorem (decide if a language has the nontrivial property P)" -- Rice's Theorem is not a problem. "We want to reduce Rice's Theorem to the Halting Problem" -- therefore, this makes no sense. $\endgroup$ – Raphael May 28 '16 at 1:24
3
$\begingroup$

Your question contains a few hints at misunderstandings of the fundamentals that would take several pages to address. So let's focus on your final question:

Is it actually possible to use Rice's theorem to prove that the halting problem is undecidable?

No. Rice's theorem can only be used to show undecidability of index sets and the (usual) Halting problem can not be expressed as such. For details, see here and here.

$\endgroup$
0
$\begingroup$

Actually Rice theorem is a generalisation of the Halting problem, so if you can assume Rice theorem you have the Halting problem as a direct consequence: Halting is a property of the function computed by the TM, and it is therefore undecidable by Rice theorem. your proof scheme tries to do the opposite: prove Rice theorem from the undecidability Halting problem, which is a more difficult (but not too much, see for instance here).

$\endgroup$
  • $\begingroup$ "Actually Rice theorem is a generalisation of the Halting problem" -- that's not even wrong. $\endgroup$ – Raphael May 28 '16 at 1:21
  • $\begingroup$ "Halting is a property of the function computed by the TM, and it is therefore undecidable by Rice theorem" -- wrong. Rice's theorem does not apply. $\endgroup$ – Raphael May 28 '16 at 1:22
  • $\begingroup$ Isn't the halting problem's undecidability used in the typical proof of Rice's theorem? So using Rice's theorem to prove the halting problem undecidble would end up being circular logic? $\endgroup$ – jmite May 28 '16 at 1:24
  • $\begingroup$ @jmite If Rice's theorem and "The Halting problem is undecidable" were actually equivalent, that wouldn't be a problem, wouldn't it? (We'd need another proof, sure, to establish the truth of both.) $\endgroup$ – Raphael May 28 '16 at 1:30
  • $\begingroup$ @Raphael yeah, there's nothing saying Rice's theorem is inherently dependent on the Halting problem, but the approach of "plug your TM into the standard proof or Rice's theorem for instant reduction" won't work. I'd be very curious to see a different proof of it! $\endgroup$ – jmite May 28 '16 at 1:49

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.