Halting problem reducing to the blank tape halting problem

Short version first: The typical reduction for this problem assumes that we can decide the blank tape halting problem, but this gives us a way to decide the halting problem (which in this situation we already know is undecidable). It does so by taking the input to the normal halting problem, and making a new TM that always starts with a blank tape, and writes the normal halting problem input to the tape as its first set of steps – so if this modified machine halts when starting with an empty tape, the normal halting problem input halts with whatever its input. Therefore we can’t decide the blank tape halting problem. Now, with some formality. We have two languages:

• $HALT_{TM} = {langle M,wrangle mid M text{ is a Turing Machine that halts on input } w}$
• $BLANKHALT_{TM} = {langle Mrangle mid M text{ is a Turing Machine that halts on input } varepsilon}$

Lemma. $BLANKHALT_{TM}$ is undecidable.

Proof.
We already know that $HALT_{TM}$ is undecidable. We show that $BLANKHALT_{TM}$ is also undecidable by reduction from $HALT_{TM}$ (i.e. we show that if we could decide $BLANKHALT_{TM}$, we could decide $HALT_{TM}$). Assume (for contradiction) that $BLANKHALT_{TM}$ is decidable, and we therefore have a Turing Machine $T$ that decides it. Using $T$, we can construct a Turing Machine $R$ that decides $HALT_{TM}$ where $R$ is:

• On input $langle M, wrangle$
  1. Construct a new Turing Machine $M_{w}$ that does the following:
     • Starts with a blank tape (or rejects otherwise).
     • Write $w$ to its tape.
     • Moves its head back to the start, and from here just copies what $M$ does.
  2. Run $T(langle M_{w}rangle)$, if $T$ accepts $langle M_{w}rangle$, accept, otherwise reject.

But this would decide $HALT_{TM}$, which we know is undecidable, so $T$ can’t exist and $BLANKHALT_{TM}$ is also undecidable. $Box$ Again, note precisely what each machine is doing:

• $R$ decides $HALT_{TM}$, with input $langle M,wrangle$.
• $T$ decides $BLANKHALT_{TM}$ by assumption.
• $M_{w}$ is basically a wrapper for the input $M$ given to $R$ that starts with a blank tape, but as its first actions writes the other input $w$ to its tape – so it starts with a blank tape, but it really does what $M$ does on input $w$.

Note that we “run” neither $M$ nor $M_{w}$, we just construct their descriptions, and give those as input strings to $R$ and $T$ respectively.