1

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?

jreing
  • 3,297
  • 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 09:34

1 Answers1

2

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

Xoff
  • 10,310
  • 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 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
  • OK, so just replace $\varphi_x(y)$ by $U\langle x,y\rangle$ (with $U$ being the universal TM) in my explanations above and $0$ by reject and $1$ by accept. – Xoff Dec 25 '14 at 15:38
  • So A is the set of all i's for which the Universal machine with input <i,i> rejects? From what we defined the first parameter to U should be a machine encoding and the second some string of input, what is $i$ here then? – jreing Dec 25 '14 at 15:41
  • you're right, $i$ is both program and data. This is the heart of computability : considering input data as machine encoding. – Xoff Dec 25 '14 at 15:42
  • $\varphi_C$ is the "decider" of C? (if it were decidable) – jreing Dec 25 '14 at 15:48
  • Yes $\varphi_c$ is the decider of the recursive set (capital) $C$, and (small) $c$ is the string that encodes the machine $\varphi_c$. By definition, $C$ is a recursive set, so it is decidable. – Xoff Dec 25 '14 at 15:50
  • Got it, thanks!!! – jreing Dec 25 '14 at 16:01