Halting problem reducing to the blank tape halting problem

Question

I was going through my book of proof and I find very confusing its definition, so I would like someone to help me in understanding this.

• The blank tape problem takes a machine and an empty tape and tells if this machine halts or not
• We prove it is unsolvable by proving it reduces to the halting problem

Whenever I read online, I read that we we write the input on the tape and we run this on the halting problem.

• How do we construct the reduction?
• Why do we write the input on the tape?
• Isn't this all about having an empty tape?

update: I think my misunderstanding is in the definitio of input and tape

Answer 1

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,w\rangle \mid M \text{ is a Turing Machine that halts on input } w\}$
• $BLANKHALT_{TM} = \{\langle M\rangle \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, w\rangle$
  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,w\rangle$.
• $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.