# Example for 2 disjoint languages that cannot be separated by a decidable language

Question: Let A, B be languages such that A ∩ B = ∅. Say that a language C separates A and B if: A ⊆ C and B ⊆ $C^c$. Describe two languages A, B ∈ RE, that cannot be separated by any C, such that C ∈ R. R is the class of decidable languages and RE is that class of Recursively Enumerable languages.

Thoughts: First I thought about taking language and it's complement- But I've read that both language and complement cannot reside at the same time in RE. Second try: (on $\Sigma=${a,b,c}) (M is a TM)

A={$<M>$ | $L(M) \subseteq a^*$} (we've seen in class this is undecidable)

B={$<M>$ | $L(M) \subseteq b^*$}

C={$<M>$ | $L(M) \subseteq a^*c^*$}

So C is also in RE as I see it, But I'm afraid also that $C^c$ is also in RE which may destroy my idea. Is this a good direction? Other suggestions?

• You probably mean $A \subset C$ and $B \subset C^c$. Otherwise you can always take $C =\Sigma^\ast$. Also: What are R and RE? – PhoemueX Dec 24 '14 at 12:44
• yes, I fixed that now (I forgot to put the compliment on C). R is the class of decidable languages and RE is that class of Recursively Enumerable languages. – jreing Dec 25 '14 at 9:34

## 1 Answer

Consider an acceptable programming system $\varphi_i$ for $i\in\mathbb N$.

1. Let $A=\{i\;|\;\varphi_i(i)=0\}$
2. Let $B=\{i\;|\;\varphi_i(i)=1\}$

$A$ and $B$ are RE.

Suppose there is a recursive set $C$ that separates $A$ and $B$. As $C$ is recursive, there is $c$ such that $\varphi_c(x)=1$ if $x\in C$ else $0$

Then $$\varphi_c(c)=1 \Rightarrow c\in B \Rightarrow c\notin C\Rightarrow \varphi_c(c)=0$$

$$\varphi_c(c)=0 \Rightarrow c\in A \Rightarrow c\in C\Rightarrow \varphi_c(c)=1$$

This is impossible : there is no such recursive set $C$.

• Hi, thanks for the reply. We haven't studied the subject of acceptable programming systems. I also didn't understand how C is defined. Could you please elaborate? – jreing Dec 25 '14 at 14:05
• We suppose that $C$ exists, and from that we prove a contradiction, so $C$ can't exist. If you didn't see what is aps, did you at least see what is a universal machine that can simulate all other machines ? – Xoff Dec 25 '14 at 15:22
• yes we saw the Universal Machine. – jreing Dec 25 '14 at 15:32
• How did you define it ? So I can use a definition you know. – Xoff Dec 25 '14 at 15:33
• Universal Turing Machines Algorithm (Universal TM U) On input <M, w>, where <M> and w are binary strings separated by 111. Checks that <M, w> is a proper encoding of a TM. Emulate M(w) 1. Accept, if M enters its accept state 2. Reject, if M enters its reject state – jreing Dec 25 '14 at 15:35