# How to reduce a problem?

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?

• You are thinking in the right direction, there is no systematic way of solving these problems, but there is a bag of tricks. Oct 12, 2018 at 6:44
• 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}}$". Oct 12, 2018 at 6:47
• @AndrejBauer what i meant was taking M from $HALT_{TM}$ and creating a another machine that deletes the tape and then run like M Oct 12, 2018 at 7:18
• Our reference question may help.
– Raphael
Oct 12, 2018 at 11:40

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.