The Gateway to Computer Science Excellence

+51 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?

- $L$ is recursively enumerable, but $L'$ is not
- $L'$ is recursively enumerable, but $ L$ is not
- Both $L$ and $L'$ are recursive
- Neither $L$ nor $L'$ is recursively enumerable

0

isn't this explanation right?

L0 and L1are complement of each other.

L0 is halting problem and which is REL and so L1 is its complement which is non REL.

so union of both i.e.L=L0 U L1 comprises of set of all REL and non REL languages.

and therefore Neither L nor L' is recursively enumerable.

option D)

correct me if i m wrong????

L0 and L1are complement of each other.

L0 is halting problem and which is REL and so L1 is its complement which is non REL.

so union of both i.e.L=L0 U L1 comprises of set of all REL and non REL languages.

and therefore Neither L nor L' is recursively enumerable.

option D)

correct me if i m wrong????

0

@Arjun sir

L0=undecidable but RE

L1=undecidable and not RE

L=*RE union not RE* gives **universal set which is undecidable but RE**

complement of L will be not RE

wht is wrong with this ?pls check

+22

@set Sehwag .is north Indian. Dravid is not a North Indian. Now does both of them combined give the whole India? Your explanation is exactly analogous to this.

+7

$\text{Two points to be noted here:}$

**1.** If the languages $L_0$ and $L_1$ were

$L_0$={⟨M,w⟩∣M halts on w}

$L_1$={⟨M,w⟩∣M does not halts on w}

Then $L=L_0 ∪ L_1$ will be regular, i.e. **Σ* **as both the languages are complement of each other.

2. $L_1$={⟨M,w,1⟩∣M does not halts on w} is **NOT RE** Because to tell TM M doesn't halt on W, TM has to halt first. an this case will never happen.

$L_0$={⟨M,w,0⟩∣M halts on w} I think language is **R.E**

So, overall $L=L_0 ∪ L_1$ = RE U NOT RE = NOT RE, **hence, L is a NOT RE language.**

+1

Manu this wont work here Union of RE and Non RE is Non RE as upper bound i.e. we are sure about this but this can be RE also.

0

@Manu yes, you cannot use the last statement. The $L_0$ you told is r.e. and $L_1$ is not r.e. but their union is regular.

0

@Anu

Tell any example where the one language is RE and the other language is NOT RE, both are not the complement of each other and their UNION is RE?

Tell any example where the one language is RE and the other language is NOT RE, both are not the complement of each other and their UNION is RE?

0

@Arjun Please, tell me any example where the one language is RE and the other language is NOT RE, both are not the complement of each other, and their UNION is RE?

0

@arjun sir, @manu sir, I don't understand the first example of manu sir,

How L0 U L1 is £* (All possible string)?

For some string of 0, 1 ,we don't have any encoding of TM but for every TM we have encoding.

@arjun sir, it is just like the example of shewag and Dravid you gave.

How L0 U L1 is £* (All possible string)?

For some string of 0, 1 ,we don't have any encoding of TM but for every TM we have encoding.

@arjun sir, it is just like the example of shewag and Dravid you gave.

+1

@Hemant just consider the universal set as the set of valid TMs and not any string. Checking this can be done by an automata and basically we are just removing a regular set from the universal set of all binary strings.

0

@arjun sir, you mean set of all binary string - (subtract) set of all valid TM is regular. But How?

Set of all binary string is regular. Set of all valid TM is countable.

Set of all binary string is regular. Set of all valid TM is countable.

+1

@Hemant it's a trivial problem to check if a given encoding is a valid encoding of a T.M or not, it can be checked easily. Being a TM, it should have at least 2 states, at least one should be accepted and one rejected state. it should have transition function etc..

A TM can also be represented by using bits, and a TM has many parameters such states, input symbols, tape symbols, final state, we can represent them in bits and can separate them using #,

**For example** if a string 01 is inputted to the UTM, UTM can reject it as it can not be a valid encoding to a TM.

So, when the encoding of a TM is inputted to the UTM, first UTM checks if it's a valid encoding or not, and it's not then UTM simply rejects it else UTM proceed further.

(or)

As Arjun said, just consider the universal set as the set of valid TMs.

+70 votes

Best answer

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$

0

@arjun sir.. Why option c is not the answer?

If we are able to solve the halting problem with the given configuration then they must be recursive... Isn't it?

If we are able to solve the halting problem with the given configuration then they must be recursive... Isn't it?

–1

@gatecse So basically what you're trying to say is if $T$ accepts $<M,w,1>$ (a case of $L$), it will halt, but it should not, as $<M,w,1>$ says $M$ doesn't halt on $w$, right? and we can prove the same for $\overline{L}$ too, that's why both $L$ and $\overline{L}$ aren't R.E.

I can just say this: "If A is reducible to B and B is undecidable, then A is undecidable"

Clearly, $L$ can be reduced to the halting problem, which is undecidable, therefore $L$ is undecidable.

I can just say this: "If A is reducible to B and B is undecidable, then A is undecidable"

Clearly, $L$ can be reduced to the halting problem, which is undecidable, therefore $L$ is undecidable.

+1

@Arjun Sir,

Can i say that since Halting TM is undecidable and this L=L0 U L1 an solve this halting problem therfore, this L is undecidable?

Can i say that since Halting TM is undecidable and this L=L0 U L1 an solve this halting problem therfore, this L is undecidable?

+1

@arjun dir,

will L1 also accept/contain invalid TM ecodings ? or only TMs which dont halt,

then only the argument that union of L0 & L1 is not Universal set sigma star, else L is only containing set of TMs which either halt or not, that are the complete set of all VALID TM encoding,

will L1 also accept/contain invalid TM ecodings ? or only TMs which dont halt,

then only the argument that union of L0 & L1 is not Universal set sigma star, else L is only containing set of TMs which either halt or not, that are the complete set of all VALID TM encoding,

0

0

ok so.. can this question be broken down to this much simplicity....

TM halts for <M,w,0>... L0

TM doesnt halts for <M,w,1> .... L1

when we take union of both these ... we get the language L .

now for L to be Recursively Enumerable , it must accept/halt for all strings in L.

since L1 , is there .. so it is safe to say that there are strings in L for which the TM does not halt ..which is against the definition of RE.

hence it is not RE .. similarly we can prove that its complement is not RE .

AM I CORRECT ?? someone pls verify !

TM halts for <M,w,0>... L0

TM doesnt halts for <M,w,1> .... L1

when we take union of both these ... we get the language L .

now for L to be Recursively Enumerable , it must accept/halt for all strings in L.

since L1 , is there .. so it is safe to say that there are strings in L for which the TM does not halt ..which is against the definition of RE.

hence it is not RE .. similarly we can prove that its complement is not RE .

AM I CORRECT ?? someone pls verify !

0

@Arjun sir L0 part of the above language is re and L1 part is not re right?

halting problem is re as we can have a universal turing machine which simulates the yes instances of the turing machines and say YES to them but not the ones which are no instances

and coming to L1 we can never say a Turing machine doesn't halt on an input just after few seconds of the declaration it might halt so we cant even say yes hence not re so this says that L is not recursively enumberable and similar explanation for L COMPLEMENT

halting problem is re as we can have a universal turing machine which simulates the yes instances of the turing machines and say YES to them but not the ones which are no instances

and coming to L1 we can never say a Turing machine doesn't halt on an input just after few seconds of the declaration it might halt so we cant even say yes hence not re so this says that L is not recursively enumberable and similar explanation for L COMPLEMENT

0

Obviously $L_0$ is r.e. and $L_1$ is not r.e. But when we take their union, it just becomes a new language and this can even be regular.

0

@Arjun sir what i meant is if we have both the set of string in the languages we can accept all the instances of L0 with yes and we cant say yes to even one instance of L1 so on the whole we cant say yes even to some instances hence it is not RE

+1

I have a silly doubt. For L' , explanation is given considering it as L0' U L1' but it should be L0' intersection L1' right ?

+1

@Arjun Sir, can we follow this approach for solving this question?

Language L0 is recursively enumerable since we can enumerate all the encoding of the turing machines that halt on input string w. But L1 is not recursively enumerable since there is no way to enumerate the strings of L1 as we wont ever know whether a turing machine will ever halt for a string w or not. Now as L is union of recursively enumerable and a non r.e language, so L will be a non r.e language. As L is non r.e, so consequently L' is also non r.e.

Language L0 is recursively enumerable since we can enumerate all the encoding of the turing machines that halt on input string w. But L1 is not recursively enumerable since there is no way to enumerate the strings of L1 as we wont ever know whether a turing machine will ever halt for a string w or not. Now as L is union of recursively enumerable and a non r.e language, so L will be a non r.e language. As L is non r.e, so consequently L' is also non r.e.

0

@Somoshree When we take union of 2 non recursively enumerable languages, the result can even be a recursive language. So, what you told won't work.

0

i am unable to understand question

does it say ---

L0 - turing machine that can say YES or NO on "if it halts on w"

L1 - turing machine that can say YES or NO on "If it doesn't halt on w"

does it say ---

L0 - turing machine that can say YES or NO on "if it halts on w"

L1 - turing machine that can say YES or NO on "If it doesn't halt on w"

0

If *$T$* accepts the triplet $<M,w,1>$, it means *$M$* doesn't halt on $w$ => we have solved halting problem.

How is this true? Can you please elaborate sir?

0

@Arjun sir, Can I say like this -

L = L0 U L1, so L is set of strings where M halts on some string & doesn't halt on some string.

Now if I can give this L into a UTM( universal turing machine) then, that UTM will definitely hatls for L0 & for L1 it may or may not halts.

Now suppose L = $L_{u}$ ( language accepted by UTM).

as per the definition we know that $L_{u}$ is R.E language, So complement($L_{u}$) = non- RE language.

thus option A is correct.

L is R.E, but L' is not R.E.

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

+5

You ignored the 0 and 1 at the end of the language description. Because of them, the union won't be universal set.

+2

OK, you mean ~L will be Empty(and hence recursive) but L is not universal as some of the elements like (M,w,1)(where M halts on w) and (M,w,0)(where M does not halts on w) are missing from their union and hence it is NonRE..isn't it?

+2

Yes. L is not universal as those elements you mentioned are missing. For the same reason ~L is not empty also. But this doesn't make neither L nor ~L not RE. We can reduce complement of RE to both L and ~L and that makes both not RE.

0

Yess ~L is also not empty :). But would you like to shed some light on the the way you transform the RE's complement into L or ~L. The way I think both of them are NonRE is combination of some RE language and some NonRE language will always be NonRE unless their union is Universal!..isn't it correct?. this question seems to be way too much tricky!

+2

I don't think your assumption is correct. Though not trivial it must be possible to give an example where your assumption won't hold. You can read the posted answer for this question. You may find it easy :)

0

@gatecse what is the significance of 0,1 bits , and how union of re and not re work , plz explain in simple language.

+1 vote

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

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

0

Sir I am not sure Can we go in this approach ?

If L_{0} U L_{1} is recursive enumerable, it means we can find out for all w ϵ **Σ***, whether M halts or does not halt. This means that if L_{0} U L_{1} is recursive enumerable, the halting problem would be decidable. There fore L= L_{0} U L_{1} is not recursive enumerable.

But complement of L = L_{0 }(comp) [INTERSECTION] L_{1} (comp) = ϕ , which is a regular language and hence RE.

So correct option is B. L comp is RE but L is not RE

Sir pls answer as early as possible.

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

52,345 questions

60,469 answers

201,795 comments

95,272 users