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

  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael Jan 9 '18 at 6:37
  • $\begingroup$ sure sir i will change it $\endgroup$ – venkat Jan 9 '18 at 8:02
  • $\begingroup$ @Raphael sir please help me understand the complement of this language .. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ sir i understood the proof for L but what is L complement just give a hint .. $\endgroup$ – venkat Jan 9 '18 at 10:15
  • $\begingroup$ thanks for bearing a lot of patience i am actually a very beginner in this concepts and i think these are tough for beginners like me . i was not thaught these concepts in my college sorry to disturb .u people are experts in ur fields i spent a lot of time from yesterday on understanding this L' but couldnt what my doubt is if we take the complement of L in form of set notation which is L1' intersection L2' which can be even a empty set right ? how can we gaurentee that the intersection in this case in nonempty set and please explain how this set is generated sorry to disturb $\endgroup$ – venkat Jan 10 '18 at 10:50
  • $\begingroup$ 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). $\endgroup$ – fade2black Jan 10 '18 at 11:02
  • $\begingroup$ Also if $A$ and $B$ have no common elements then their intersection is also is empty. $\endgroup$ – fade2black Jan 10 '18 at 11:02
  • 1
    $\begingroup$ 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. $\endgroup$ – fade2black Jan 10 '18 at 11:47

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.