My assignment says:

"Determine if the following statement is correct: If $A$ and $A \cup B$ are decidable, then $B$ is decidable."

The solution says:

"Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ is the halting problem with input $\epsilon$ and $A = \{0,1\}^*$, then $A$ and $A \cup B$ are decidable and $B$ is undecidable.

My question is:

How can $A \cup B$ be decidable if $B$ is undecidable? If for example $b \in B$ then $b \in A \cup B$ but a Turing Machine may not halt on $b$ because $B$ is undecidable, then how can $A \cup B$ still be decidable with $b \in A \cup B$ ?

  • 2
    $\begingroup$ Take $A = \{0,1\}^*$. $\endgroup$ – Yuval Filmus Sep 16 '19 at 10:10
  • $\begingroup$ If it’s not clear enough (since it was mentioned in the solution you were given): in this case A union B is decidable no matter what B is, because A = A union B = all possible strings. The Turing machine can halt immediately without caring about B at all. $\endgroup$ – gnasher729 Sep 16 '19 at 10:37

If $A=\{0,1\}^*$ then $A\cup B=\{0,1\}^*$, regardless of what $B$ is. $\{0,1\}^*$ is decidable, and choosing to express it as something involving undecidable things doesn't change that fact.

The question "Is $w$ in $A\cup B$?" is equivalent to "Is at least one of the following statements true? $w$ is in $A$; $w$ is in $B$; $w$ is in both $A$ and $B$?" In the case $A=\{0,1\}^*$, we can answer "Yes, $w$ is in $A$" and the rest of the questions are irrelevant. It doesn't even matter if we can't answer "Is $w$ in $B$?", because we don't need to.

Here's a more practical example that might help. Suppose I give you a number $x$ and ask you "Is $x\in\text{Integers}\cup\text{Primes}$?" Figuring out if a large number is prime is quite difficult, but you can easily answer my question by checking if $x$ is an integer. You can ignore the "prime" part completely.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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