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?

  • $\begingroup$ 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? $\endgroup$ – PhoemueX Dec 24 '14 at 12:44
  • $\begingroup$ 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. $\endgroup$ – jreing Dec 25 '14 at 9:34

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$.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – jreing Dec 25 '14 at 14:05
  • $\begingroup$ 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 ? $\endgroup$ – Xoff Dec 25 '14 at 15:22
  • $\begingroup$ yes we saw the Universal Machine. $\endgroup$ – jreing Dec 25 '14 at 15:32
  • $\begingroup$ How did you define it ? So I can use a definition you know. $\endgroup$ – Xoff Dec 25 '14 at 15:33
  • $\begingroup$ 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 $\endgroup$ – jreing Dec 25 '14 at 15:35

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.