14,940 views

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

y not c option is ans ?????????
whats the mening of this question? what actually is L1 and L0? can someone plzz explain to me??
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????

@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

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

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

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.
@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.
@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?
@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?
For that example just delete one string from $L_0$ or $L_1$
@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.
@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.
@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.

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

L0 is a language which contains a set of all strings which are "encoding of Turing machine which halts on string w followed by string w and then followed by bit 0"
What would you say for L={<M>| there exists an input whose length is less than 100, on which M halts}

Is L recursively enumerable or recursive?
edited by

@Arjun Sir, there exist some cases for RE languages as well where the problem is partially-decidable i.e the problems are not recursive and TM may halt or not but there exists TM software for them. Now, if we consider the L1 case, how can we directly state that it is NOT RE langauge when there exists TM atleast for the problem.

As per me,

L0 = RE(undecidable)

L1 = RE but not REC(undecidable)

I am not able to understand why people are saying that L1 is NOT RE?

@Shimpy Goyal

Since L0 ∪ L1= L  is a non halting language, and we know that for every Recursive language Turing machine halts. Therefore L cannot be Recursive and neither its compliment can.

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$

by

@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?
@Anirudh Absolutely.
@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,
@Nit9 Yes, you are correct-- I considered only valid encodings of TMs. I'll add this in the answer.
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 !
@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
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.
@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
I have a silly doubt. For L' , explanation is given considering it as L0' U L1' but it should be L0' intersection L1' right ?
@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.

if L is not RE L' can be RE

watch this video u will get some insight

@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.
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"
@Arjun sir thanks for this lovely solution and comments.i got this after many no of reads

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?

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

Sir ,

I havenot got this line

Hence, if L is recursively enumerable we can solve halting problem  ⇒L is not recursively enumerable.

How two contradictory statement can be same at a time??

Halting problem is RE, then how will it be non-RE at the same time?

What does bit i signify here? They didn't clearly explain what it stands for?

srestha in the answer they have reduced the halting problem to L

L is RE  we can solve it for the halting problem

but the halting problem itself is unsolvable so L is not RE

edited by

@Arjun

Thanks for this wonderful explanation! Other websites usually “dumb” it down and end up teaching wrong concepts.

Could you please clarify the following?

You say:

If T accepts the triplet ⟨M,w,0⟩, it means M halts on w => we have solved halting problem

Also that:

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.

I think: the halting problem $\{< M,x >:M$ halts on input $x \}$ is recognizable i.e. given a machine M and a string w, I can always get acceptance if M stops on w by simply running it. So even if $T$ accepts $<M, w, 0>$ we have not really “solved” the halting problem because the machines $M’$ that don't halt on $w$ will need to be rejected by this machine $T$ (for solving halting problem).

I understand your proof. I think a few more details can help beginners like us to fill in the gaps. Please feel free to point out any mistakes:

• Assume $L$ is recognizable (we want to prove the opposite by contradicting this)
• A recognizable $L$ has a TM $M_\cup$ that can accept and halt on $x \in L$
• We take two copies of this machine $M_\cup$ and run the inputs $<M, w, 0>$ and $<M, w, 1>$ in parallel in this machine $M_\cup$
• If the first copy of $M_\cup$ halts, we can conclude that $M$ halts on $w$ (print "yes")
• If the second copy of $M_\cup$ halts, we can conclude that $M$ does not halt on $w$ (print "no")
• Either $M$ halts or does not halt on $w$
• In this parallel consruction one of the machines must halt and so $M_\cup$ halts for every input of $M, w$
• This implies that for any $M, w$ we have a machine $M_\cup$ halts (with acception or rejection)
• note that a turing machine $M_0$ for $L_0$ also halts for inputs $<M,w,0>$ when $M$ halts on $w$ but $M_0$ does not halt for any $x \not \in L_0$. So $L_0$ is recognizable but not decidable
• but this result about $M_\cup$ is different: it says we can halt for every $M,w$ which means $M_\cup$ decides the halting problem: $\{<M,w> |$ does $M$ halt on $w? \}$. This machine $M_\cup$ prints "yes" if it does, and prints "no" if it does not.
• The halting problem above is known to be undecidable
• This is what creates the contradiction and thus there is no machine $M_\cup$. Remember that even though $M_\cup$ decides the halting problem, it only recognizes $L$ (as we stated). So the conclusion is that $L$ is not recognizable.

Since $L$ is not recognizable, we cannot say anything about $\bar{L}$ directly. For the proof of $\bar{L}$, again we start with the assumption that $\bar{L}$ is recognizable (we'll end up at a contradiction)

• Since $\bar{L}$ is recognizable there exists a machine $\bar{M}$ that accepts and halts for $\forall x \in \bar{L}$.
• What strings (or machines) are part of $\bar{L}$?
• Say we have a machine $M$ that does not halt on $w$
• $<M, w, 1>$ belongs to $L_1$ as per definition but what about $<M, w, 0>$?
• Note that $<M, w, 0>$ does not belong to $L_1$ (because it ends with $0$) and it also cannot belong to $L_0$ because $M$ does not halt on $w$ (as per definition $<M,w,0>$ belongs to $L_0$ when $M$ halts on $w$). So it belongs to neither $L_0$ nor $L_1$ and thus belongs to $\bar{L}$
• Say we have a machine $M$ that halts on $w$. With a similar reasoning as above, we can prove that $<M, w, 1>$ belongs to $\bar{L}$
• We are now ready to run some inputs in our machine $\bar{M}$.
• We have two copies of $\bar{M}$ and we run the input $<M,w,0>$ and $<M,w,1>$ on these two copies in parallel:
• We know that $\bar{M}$ halts for any input $x \in \bar{L}$.
• Say the first copy halts:
• This means $<M,w,0>$ is part of $\bar{M}$ and as we proved before this is only possible if $M$ does not halt on $w$.
• We print "no" when the first copy halts
• Say the second copy halts:
• This means $<M,w,1>$ is part of $\bar{M}$ and as proved before this is only possible if $M$ halts on $w$.
• We print "yes" when the second copy halts
• We now have a machine $\bar{M}$ that can take inputs $M,w$ and print "yes" if $M$ halts on $w$ and prints "no" if $M$ does not halt on $w$. Thus this machine $\bar{M}$ decides the halting problem, which is a contradiction: no machine can decide the halting problem.
• This implies $\bar{M}$ cannot exist.
• This implies no machine can recognize $\bar{L}$.

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.

You ignored the 0 and 1 at the end of the language description. Because of them, the union won't be universal set.
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?
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.
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!
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 :)
will L1 also accept/contain invalid TM ecodings ? or only TMs which dont halt,

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

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

You should watch this playlist

okkkkkkk sir.. if there is something wrong in my answer , plz point it out....
edited by

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

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

But complement of L = L(comp) [INTERSECTION] L1 (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.

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. 