edited by
23,897 views
70 votes
70 votes

Define languages $L_0$ and $L_1$ as follows :

$L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\} $

$L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$

Here $\langle M, w, i \rangle$ is a triplet, whose first component $M$ is an encoding of a Turing
Machine, second component $ w$ is a string, and third component $i$  is a bit.

Let $L = L_0 \cup L_1$. Which of the following is true?

  1. $L$ is recursively enumerable, but $L'$ is not
  2. $L'$ is recursively enumerable, but $ L$ is not
  3. Both $L$ and $L'$ are recursive  
  4. Neither $L$ nor $L'$ is recursively enumerable
edited by

4 Answers

Best answer
93 votes
93 votes

Both $L$ and $Lʼ$ are undecidable and not even semi-decidable (not recursively-enumerable). Because halting problem can be solved with both $L$ and $Lʼ$.

Halting problem can be stated as follows: A machine $M$ and a word $w$ are given. You have to tell, if $M$ halts on $w$.
 
So, to solve halting problem $\langle M,w\rangle$ using $L$, just give $\langle M,w,0\rangle$ and $\langle M,w,1\rangle$ to two instances of $T$ which is the assumed Turing machine for $L$. If $T$ accepts the triplet $\langle M,w,0\rangle$, it means $M$ halts on $w$ => we have solved halting problem. If $T$ accepts the triplet $\langle M,w,1\rangle$, it means $M$ doesn't halt on $w$ => we have solved halting problem. We know that either $\langle M,w,0\rangle$ or $\langle M,w,1\rangle$ is in $L$. So, if $L$ is recursively enumerable, $T$ is bound to stop on at least one of these inputs ($TM$ for a recursively enumerable language stops and accepts, when provided with a word in its language).  

Hence, if $L$ is recursively enumerable we can solve halting problem  $\Rightarrow L$ is not recursively enumerable.
Similarly, we can also show that halting problem can be solved with $L'$. (shown at end)

Hence, neither $L$ nor $L'$ is recursively enumerable.


To solve halting problem $\langle M,w\rangle$ using $L'$, just give $\langle M,w,0\rangle$ and $\langle M,w,1\rangle$ to two instances of $T'$ which is the assumed Turing machine for $L'$. If $T'$ accepts the triplet $\langle M,w,0\rangle$, it means $M$ does not halt on $w$ => we have solved halting problem. If $T$ accepts the triplet $\langle M,w,1\rangle$, it means $M$  halt on $w$ => we have solved halting problem. We know that either $\langle M,w,0\rangle$ or $\langle M,w,1\rangle$ is in $L'$. So, if $L'$ is recursively enumerable, $T'$ is bound to stop on at least one of these inputs ($TM$ for a recursively enumerable language stops and accepts, when provided with a word in its language).

Hence, if $L'$ is recursively enumerable we can solve halting problem   $\Rightarrow L'$ is not recursively enumerable.


PS: If the bit part of the triplet is absent then $L_0$ is halting problem and $L_1$ is its complement and $L_0 \cup L_1 = \Sigma^*$, which is regular. Lets see how it happens. 

Let the alphabet set be $\{0,1\}$. Now for any string like $0010101$ there are only two options-  belong to $L$ or belong to $L'$ as this is what complement says. Now, lets take the case for $L_0$ and a string $001\dots10-01-1$, ("-" shown for notation purpose only) where the  first component describes a TM $M$  followed by input "$w = 01$" and last bit "1". Now suppose $M$ halts on "$01$". Still the given input is not in $L_0$ as the last bit is "$1$" and not "$0$" as required by $L_0$. So, this input must be in $L_0'$. But since $M$ halts on $w$, this input is not in $L_1$ either. Similarly, we can get an infinite set of strings which does not belong to both $L_0$ and $L_1$ and this makes their union not $\Sigma^*$ but an irregular (not r.e. as proved earlier) set. If the last bit is removed from the definition of $L_0$ and $L_1$, then any string should be present in either $L_0$ or $L_1$ and their union would be $\Sigma^*$. 

Correct Answer: $D$

edited by
3 votes
3 votes
C...as both L0 and L1 are complement of each other and so their union will be universal set which is Regular(and so recursive), and there intersection is Empty set which is also regular.
edited by
1 votes
1 votes
According to me Answer is Options(A).

 its strt Forwrd..

here L0 is Recursive bcoz Machine halts on string W.

L1 is Recursively Enumerable Bcoz Machine doesnt halts on String W.

So;  L=L0 UNION L1 will be Recursively Enumerable. and complement of Recursively Enemerable lang is Not Recursively enmerable..

Hence L is Recursively Enumerable and L' is not Recursively enumerable..........

 

(If Anything Wrong , Plz comment.....)
1 votes
1 votes

The most important part in this question is to understand the usage of bit.

L0 contains the <M,w> patterns such than w belongs to M and bit is 0 or some <M, w> patterns such that w doesn't belongs to M but halt happens and bit is 0.

L1 contains the complement of L0, but bit pattern must be 1. So, technically L1 is not complement of L0.

Answer:

Related questions