Interesting Decidability Problem

The Question

For any languages $S, T$, if $S \setminus T$ is decidable, is it true that both $S, T$ will be decidable?

Answer

No, as we can prove here with two counter examples:

Simple case

First, consider the case where $S$ is some undecidable language, which we know exists. Let $T = S$, then $S \setminus T = \emptyset$ is the empty language. We can decide this language with a decider that rejects any input. In this case, the empty language $S \setminus T$ is decidable by this decider, while $S, T$ are undecidable.

Complex case

Again, we can show this with an example where $S$ and $T$ are strictly different languages: Consider language $L = \{ \langle M_{all}, 0 \rangle \}$, where $M_{all}$ is a TM that accepts all inputs. We can decide this language by a Turing Machine $M_{Mall}$:

• Define $Q_L$ as a TM that takes input $\langle M, x \rangle$, a tuple of machine $M$ and input value $x$.
• We hard code the binary of $M_{all}$ and $x$ into $Q_L$
• If the input $\langle M \rangle = \langle M_{all} \rangle$ and $\langle x \rangle = \langle 0 \rangle$, the machine accept. Otherwise reject.
• This machine inspects two finite length input strings once each in linear time and never loops, so it halts on all input.
• In fact, we can hard code this TM as two DFAs, which halt on all input.

Consider language $S = L_{HALT} = \{\langle M, x\rangle: \text{machine }M$ halts on input x. This is an undecidable language as shown in lecture (if not, soon). Since $M_{all}$ accepts all inputs, $\langle M_{all}, 0 \rangle \in S$. Then, consider $T = S \setminus L$. With a brief proof, we can show that $L = S \setminus T$. Given that $S$ is undecidable, we can now show that $T$ is undecidable as well, by proof of contradiction:

• Seeking contradiction, assume that $T$ is decidable. By definition, there is some TM $Q_T$ that decides $T$.
• Therefore, we can construct a decider $Q_S$ that decides language $S$ using $Q_T$ and $Q_L$ as follows:
• $Q_S$ accepts some input $\langle M, x \rangle$ if either $Q_T$ or $Q_L$ accepts $\langle M, x \rangle$. If both machines reject the input, $Q_S$ rejects the input.
• We can prove that $Q_S$ decides $S$: If the input is in $S$, by construction, it is either in $T$ or in $L$, so either $Q_T$ or $Q_{L}$ accepts the input, making $Q_S$ accept the input. Otherwise, if the input is in neither $T$ or $L$, both machines will reject the input, making $Q_S$ reject the input.
• $Q_S$ halts on all input because both $Q_L$ and $Q_T$ are deciders that halt on all input by definition.

We have now constructed a decider for $S$ given that $T$ is decidable. This introduces a contradiction since $S$ is undecidable. Therefore, $T$ must be undecidable as well.

Thus, we have constructed different languages $S$, $T$ such that $S \setminus T$ is decidable but neither $S$ or $T$ is decidable.