How to prove that a problem is undecidable by using the Halting problem?

Question

I cannot understand how to reduce the halting problem to a property to show that is undecidable.

For example, I have this property of a Turing Machine and I have to prove if it's recursive or not:

"M eventually enters the fifth state in its rule list when executed on an empty tape"

How can I do it? Do I have to reduce it to a halting problem or vice-versa?

Thanks in advance.

Answer 1

When you reduce problem A to problem B, you show that B is at least as hard as A. (It's sort of like a proof by contradiction: if B were any easier, then A would become just as easy.) And undecidability is about as hard as you can get, in computer science.

So what you want to do here is:

• Assume you have an oracle for the "fifth state problem"
• Show that you can solve the Halting Problem with this oracle
  • It doesn't matter how long it takes or how many times you call the oracle, for this problem (since all you care about is decidability)
• The Halting Problem is undecidable
• Therefore, the "fifth state problem" is also undecidable

Here are a few hints to get you started:

• You can reorder the states in a Turing machine without really changing anything important
• If a TM has less than five states, you can add new "dummy" states that are never used, without really changing anything important
• A TM never needs more than one halting state
• The question "does this TM halt on empty input?" is a variant of the Halting Problem that is also undecidable