0
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

It cannot be true simultaneously that A is undecidable, A can be reduced to B, and B is decidable. Assume there are three "proofs" for each of these three facts, then at least one of the proofs is wrong. Actually, at least one of the three "facts" must be wrong. At this point we don't know which one. So we would probably look at the one that has been tested the least and find an error in its proof, or show that the fact is wrong.

If "A is undecidable" is a long "known" fact that everyone trusts, then people will first check whether A can indeed be reduced to B, and whether B is indeed decidable. If no fault in the proofs can be found, to the point where we are convinced they are correct, then we would try to find a fault in the proof of "A is undecidable". And if we can't find any fault in that proof, then we repeat, but we try harder. Or we give the problem to some better mathematicians. Or many better mathematicians.

$\endgroup$
0
$\begingroup$

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.

So, no, I’d say that the situation you propose is impossible, unless something really revolutionary happens.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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