1
$\begingroup$

This question already has an answer here:

I have seen a few proofs that the Blank Tape Halting Problem is undecideable, however I'd like to check if the following is a valid proof (and if it isn't why not)

Proof: Suppose that the Blank Tape Halting problem is decideable, then there exists a universal turing machine $M$ that decides it. So given any turing machine $T$, $M$ decides if $T$ halts after being started on a blank tape.

Now let any turing machine $T$ and input $w$ be given. Construct a new turing machine $R$ (with start state blank) such that $R$ halts on a blank tape if and only if $T$ halts on $w$.

Then if $M$ takes $R$ as input, $M$ decides if $R$ halts on a blank tape and thus decides if $T$ halts on $w$. Since $T$ and $w$ were chosen arbitratily $M$ decides the Halting problem, a contradiction, so the Blank Tape Halting Problem is undecideable. $\square$.


Is there anything wrong with my reasoning above? I assume that there must be some key detail that I'm overlooking, or that my proof isn't completely rigorous

I guess the problematic argument may be the following

Construct a new turing machine $R$ (with start state blank) such that $R$ halts on a blank tape if and only if $T$ halts on $w$.

Since I haven't explicitly constructed such a turing machine $R$ in my proof above.

$\endgroup$

marked as duplicate by Thinh D. Nguyen, Yuval Filmus computability Oct 30 '18 at 4:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

You need to explain how to construct $R$. In your case this can be done formally, by constructing a machine which works as follows:

  1. Write $w$ on the input tape.
  2. Move the head back to its initial position.
  3. Transfer control to $T$.

It is not too hard to construct $R$ explicitly from $T$.

In order for your argument to go through, you need to show that this reduction is computable. Usually we describe such reductions informally and just claim (without proof) that it is computable, since actually proving such things formally is extremely technical and longwinded.

$\endgroup$
  • $\begingroup$ I have written down such a longwinded work here: cs.stackexchange.com/a/99193/90560 just several hours before this answer. And several hours later (since this answer), I post this comment pointing back to my answer. $\endgroup$ – Thinh D. Nguyen Oct 30 '18 at 2:08
  • $\begingroup$ I vote to close this as a duplicate. $\endgroup$ – Thinh D. Nguyen Oct 30 '18 at 2:13

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