Implications of Halting Problem being unsolvable?

Question

I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP).

We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is solvable. By contrapositive, we get that if HP is undecidable, then BP is undecidable as well. But now this creates an issue.

BP is just a special case of HP where the input to HP is a Turing Machine and a blank tape. Also, HP is a harder version of BP since we can get all possible tapes as input. So, just because a harder problem is unsolvable, how can we conclude that the more general form is also unsolvable.

It might be possible that we have some TM that can solve BP but cannot solve HP.

I know that both BP and HP are undecidable, but my main question is that how can we conclude via reduction that BP $\implies$ HP?

Answer 1

I have a valid reduction below, but it is all very formal, and it's not the intuition I have for this kind of problem. When I consider, is this problem decidable/NP-Complete/etc, I frame it as a challenge: somebody says I bet BP is decidable!, and I reply Oh yeah?! Well, if that were true, then I could solve HP!. And then I show how I would do that: I suppose that BP is decidable, (i.e. I accept the challenge) and then I use that to solve HP. Granted, acknowledging this takes away some of your street cred, but it does work for me.

Here's a cheat sheet:

• Show a reduction $f$ so that $HP \leq_f BP$: Hey I bet HP is decidable! Reply: Oh yeah?! Then I can solve BP like $f$

• Show that Indset is NP-Complete by reduction from 3Sat, i.e. $3Sat \leq_f IndSet$: Hey I bet IndSet is easy! Reply: Oh yeah?! Well if it were easy, then I could solve 3SAT like so! I would take my arbitrary 3SAT instance $\phi$ and transform with $f$ to an IndSet instance $f(\phi)$ and then we'll let you solve $f(\phi)$ with your supposedly fast IndSet algorithm!

I hope that if these comments do not make you laugh, at least they help you internalize the notion of what a reduction is supposed to do, and how you are supposed to make one.

Now for a valid reduction. You have reduced HP to BP via a reduction $f$ (like the one I gave for your prevous question), so if somebody asked, does $M$ halt on $w$?, then you can reduce the HP instance $\langle M, w\rangle$ to the BP instance $A=f(M,w)$ (e.g. $A$ is a TM that simulates $M$ on $w$ given the blank tape), and ask your BP machine whether $A$ halts on the blank tape. So if BP were decidable, we would have an algorithm for HP, namely the one that I just described. But we don't. So BP is not decidable.