Prove the halting problem is undecidable using Rice's theorem

Question

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?

• Raphael: You need to read this, I think.
• Raphael: "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.

Answer 1

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).

• Raphael: "Actually Rice theorem is a generalisation of the Halting problem" -- that's not even wrong.
• Raphael: "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.
• Joey Eremondi: 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?
• Raphael: @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.)
• Denis: @Raphael, I took the Halting problem to be "does $M$ halt on the empty input", which is a property of the function computed by $M$ terminates

Answer 2

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.