# complement of a NON RECURSIVELY ENUMERABLE LANGUAGE

Define languages L0 and L1 as follows :

L0={⟨M,w,0⟩∣M halts on w}

L1={⟨M,w,1⟩∣M does not halt on w}

Here ⟨M,w,i⟩is a triplet, whose first component M is an encoding of a Turing Machine, second component w is a string, and the third component i is a bit.

Let L= L0 ∪ L1. Which of the following is true?

L is not even recursively enumerable as we cannot even design an acceptor for L as even when L0 is RE L1 is not RE

but can anyone explain me what about L COMPLEMENT what is the language ??

L0'={⟨M,w,0⟩∣M doesn't halts on w}

L1'={⟨M,w,1⟩∣M halts on w} what i am working on is will there be any such encodings which satisfy both for the intersection to be non empty if there are no such encodings the set becomes empty and hence regular right ? please help

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Jan 9 '18 at 6:37
• sure sir i will change it – venkat Jan 9 '18 at 8:02
• @Raphael sir please help me understand the complement of this language .. – venkat Jan 9 '18 at 10:27

The complement of $L$ is $$\overline{L_0 \cup L_1} = \overline{L_0} \cap \overline{L_1}$$ where $\overline{L_0} = \{D \mid \text{ if } D \text{ is } \langle M,w,0\rangle \text{ then } M(w) \text{ does not halt}\}$. In other words, $\overline{L_0}$ consists of those triples $\langle M,w,b\rangle$ which does not include descriptions $\langle M,w,0\rangle$ such that $M$ halts on $w$. Similarly for $\overline{L_1}$. This post explains why both $L$ and $\overline{L}$ are not recursively enumerable.
• Let $U$ be a universal set. In particular take $U = \Sigma = \{0,1\}$. For any two subsets $A$ and $B$ of $U$ the following two equalities are always true: 1) $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and 2) $\overline{A \cap B} = \overline{A} \cup \overline{B}$. These equalities are known as DeMorgan's laws. You can spend some time to prove them (which is a simple exercise) to convince yourself. Furthermore, $\overline{A}$ is empty iff $A=U$ (is a universal set). – fade2black Jan 10 '18 at 11:02
• Also if $A$ and $B$ have no common elements then their intersection is also is empty. – fade2black Jan 10 '18 at 11:02
• It depends on your encoding. Let $T$ be a set of all pairs $\langle M,w \rangle$ (over $0$ and $1$). Next define a new set $S = T\times \{0,1\}$, which is essentially a set of all triplets $\langle M,w, b\rangle$ (where $b=0$ or $1$). Then the intersection $\overline{L_0} \cap \overline{L_1}$ is not empty. But if you define your universal set as the union of $L_0 \cup L_1$ then the intersection $\overline{L_0} \cap \overline{L_1}$ is of course empty. But in both cases $L_0 \cup L_1$ is not r.e. – fade2black Jan 10 '18 at 11:47