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
