[Solved]: Let A,B be languages. If A is decidable and B undecidable, then A reducible to B

Problem Detail: 

So I'm learning for an upcoming exam and there's a specific problem which I can't show:

Let A be decidable and B undecidable, then $A \le B$

Can someone give me a hint how to solve that? Furthermore, does that mean, that every decidable language is reducible to an undecidable language?

Asked By : but_they_should

Answered By : David Richerby

The hint is that your reduction can compute any computable function of its input. Whether an instance of $A$ is a "yes" or a "no" instance is computable by construction.

And, yes, that means that every decidable language is reducible to every undecidable language. It means that because you've assumed nothing about $A$ and $B$ except decidability of $A$ and undecidability of $B$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38085

 Ask a Question

 Download Related Notes/Documents