World's most popular travel blog for travel bloggers.

[Solved]: (Un)Decidability of disjoint decidable and undecidable sets

, , No Comments
Problem Detail: 

I thought of this question today: given are a decidable set $A$ and undecidable set $B$ for which $A \cap B = \emptyset$. Is $A \cup B$ decidable or undecidable?

I am almost sure that it is undecidable but cannot come up with an argument/proof as to why, or even a counterexample.

Asked By : Ryan

Answered By : Yuval Filmus

Hint: Suppose you could decide $A \cup B$. Using an algorithm for deciding $A$ and an algorithm for deciding $A \cup B$, can you decide $B = (A \cup B) \setminus A$?

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback