2
$\begingroup$

I am a bit confused on how to reduce a problem. I'll give an example: Let's say there is a problem called HALTEMPTY and we know it is undecidable.

  • $HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ is a Turing Machine that halts on input } \varepsilon\}$

The problem we are reducing to is

  • $HALT_{TM} = \{\langle M,w\rangle \mid M \text{ is a Turing Machine that halts on input } w\}$

So from what I think, we reduce $HALTEMPTY_{TM}$to $HALT_{TM}$ by creating a turing machine similar to $HALT_{TM}$ but it would delete the tape then run normally like $HALT_{TM}$. Am I thinking this right? Is there a systematic way of solving these type of problems?

$\endgroup$
  • $\begingroup$ You are thinking in the right direction, there is no systematic way of solving these problems, but there is a bag of tricks. $\endgroup$ – Andrej Bauer Oct 12 '18 at 6:44
  • $\begingroup$ Nitpick: "Turing machine similar to $\mathrm{HALT}_{\mathrm{TM}}$" is not a sensible phrase ebcause (1) $\mathrm{HALT}_{\mathrm{TM}}$ is not a Turing machine but a set of codes of Turing machines, and (2) what does "similar" mean here? It would be better to say "Turing machine whose code is an element of $\mathrm{HALT}_{\mathrm{TM}}$". $\endgroup$ – Andrej Bauer Oct 12 '18 at 6:47
  • $\begingroup$ @AndrejBauer what i meant was taking M from $HALT_{TM}$ and creating a another machine that deletes the tape and then run like M $\endgroup$ – defaultjay Oct 12 '18 at 7:18
  • $\begingroup$ Our reference question may help. $\endgroup$ – Raphael Oct 12 '18 at 11:40
0
$\begingroup$

You are thinking in the right direction, and you almost got it right. What we need is a partial computable map $r : \mathbb{N} \to \mathbb{N}$ such that, for all $n \in \mathbb{N}$, $$n \in \mathrm{HALTEMPTY}_{\mathrm{TM}} \iff r(n) \in \mathrm{HALT}_{\mathrm{TM}}.$$ Your instinct about having to do something with empty tapes is right, but you should follow the definitions. An element of $\mathrm{HALT}_{\mathrm{TM}}$ is a code $\langle M, w\rangle$, which means that rather than "deleteing the tape", you should provide a tape $w$. In this case, it should be the empty tape $w_\mathrm{empty}$. So we may define $$r(M) = \langle M, w_\mathrm{empty} \rangle.$$ Reduction in the other direction is more complicated, you should try to do it yourself.

$\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.