6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Actually, you are proving the blank-tape halting problem is undecidable by reducing the halting problem to it. Since reductions map instances to instances, here you need to map a pair $(M,x)$ where $M$ it a TM and $x$ the input to a TM $M'$ (and no input). What $M'$ does is just write $x$ to its tape and then do whatever $M$ would do. (This is a comment, since there must be another similar question.) $\endgroup$ – Louis Apr 11 '15 at 8:54
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am not getting the last two sentences: (1) So $M_w$ is a machine that gets an empty tape and writes w on the tape right? (2) what do you mean by ``we run neither'' $\endgroup$ – revisingcomplexity Apr 11 '15 at 9:27
  • 1
    $\begingroup$ @graphtheory92 (1) correct, so we've "artificially" created an instance of the blank tape halting problem out of the normal one (but through our trickier, it behaves almost exactly the same as the normal one). (2) $M$ and $M_{w}$, within this proof, are just descriptions of Turing Machines, we don't, for example, try to run $M$ on $w$ (this may be obvious to you, but it's a point a lot of people get stuck on - there's no simulation or running of the input machines). Really, we can't run $T$ or $R$ either - the whole point of the proof is that $T$ doesn't exist, and we already know $R$ doesn't $\endgroup$ – Luke Mathieson Apr 11 '15 at 9:59
  • $\begingroup$ Why do I not have to erase in $M_w$ input? as first thing in $M_w$ ? $\endgroup$ – revisingcomplexity Apr 11 '15 at 10:33
  • $\begingroup$ @graphtheory92 $M_{w}$ only has to start with an empty tape (hence the "or rejects otherwise" part), after the start though, it can have anything it wants. $\endgroup$ – Luke Mathieson Apr 11 '15 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.