1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
1
$\begingroup$

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
|cite|improve this answer
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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