Reduction from HALT on any string to HALT on empty string The title says it all (if I have phrased it properly). How can we show that HALT on any string is undecidable using a decider for HALT on empty string? I think this is written: $$ HALT \leq HALT_\epsilon $$ Sincerely, Frank Some additional Context: We want to use a mapping reduction, or a Turing reduction. The basic idea here is that we know $HALT$ is undecidable, so to show that $HALT_\epsilon$ is also undecidable, we construct a decider for $HALT$ by assuming the existence of some decider $R$ for $HALT_\epsilon$. If we go with a mapping reduction, we'd write some subroutine that generated instances of $HALT_\epsilon$ out of instances of $HALT$. If we succeed, then we prove that $HALT_\epsilon$ is undecidable: If $ HALT \leq HALT_\epsilon $ and $HALT$ is known to be undecidable, then $HALT_\epsilon$ is undecidable.

Suppose your original program is $\text{orig_prog}(x)$ and you want to see if it halts on some input $w$, then just make a new program $\text{orig_prog}_\epsilon(x) = \text{orig_prog}(w)$, and ask your Halt-on-epsilon oracle if this halts. In other words, create a machine that encodes your old machine running on a particular string as its no-input behavior and past that to your Halt-on-epsilon oracle.