How to reduce a problem?

Question

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?

Answer 1

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.