if there is no reduction from A to B

Question

I'm facing the following question :

If there is no $𝐴\leq_𝑚𝐵$ reduction,

does this necessarily mean that A is not decidable?

for any choice of B.

thanks in advance.

Answer 1

The language $A$ is not necessarily undecidable if we allow any arbitrary but fixed choice of $B$. For example set $B$ to be the empty language. The only language reducible to $B$ is $B$ it self.

On the other hand, if you mean there is exists a language $B$ such that $A \leq_m B$, then for each language $A$ no matter if it is decidable or not there is such a $B$, namely choose $B$ to be the language $A$ it self.

Note that the only meaningful way to read the statement, is to fix $B$ to a language that is complete for the class of decidable languages. Clearly, decidable languages are closed under$\leq_m$ reductions, however, I don't think a complete language for this class is known (or whether such a language can be constructed). However, for such a language $B$, a language $A$ is decidable if and only if $A\leq_m B$ per definition of complete languages.