# If A is reducible to B, assuming A is hard, why can't "B is easy" update our belief to A is easy?

The concept of reducibility in computability theory is very confusing for me. For example, as described in Micheal Sipser's Introduction to the theory of computation, I understand that if language A is reducible to B, then solving A cannot be harder than solving B, or in other words, solving B gives a solution to A. Then it follows that if A is hard, then B has to also be hard.

But my confusion is: if A is some undecidable problem, e.g., the halting problem, and A is reducible to B, i.e., the solution to B can be used to solve A. Then is there absolutely no way that B can be decidable? Is there no chance that we could possibly discover/invent some smart way of deciding B that can prove that our previous understanding of A is wrong?

Discovering that $$B$$ is decidable may mean one of two things:
1. There is an error somewhere: either in the proof of decidability of $$B$$, or in the proof of undecidability of $$A$$, or in the reduction from $$A$$ to $$B$$ (or, in an extreme case, in the very foundations of mathematics).
2. The algorithm used to decide $$B$$ does not conform to the usual notion of “algorithm” (i.e., it can’t be implemented on a Turing machine or any of the models equivalent to it). This is theoretically possible, although unexpected, if the Church-Turing thesis happens to be false.
In the latter case, I wouldn’t just say that our previous understanding of $$A$$ is wrong, but that our very understanding of the notion of computation was wrong (or, rather, incomplete). A whole class of problems (those that are reducible to $$B$$ but were previously thought to be undecidable) would become decidable under this new notion of algorithm. The very notion of “reduction” would change, since the newly discovered computation techniques would apply to it, too.