GATE CSE 2003 | Question: 54

Question

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?

• A. $L$ is recursively enumerable, but $L'$ is not
• B. $L'$ is recursively enumerable, but $ L$ is not
• C. Both $L$ and $L'$ are recursive  
• D. Neither $L$ nor $L'$ is recursively enumerable

Comments

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?

---

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

Answer 1

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$

Comments

L'= (L1 U L2)' =L1' ∩ L2'= ∅ which is regular ...so shouldn't L' be recursively enumerable...?   Plz explain...

---

Doesn't the language L mean, "Either machine M halts on w or machine M doesn't halts on w"? Isn't this statement is trivially true?

---

@Arjun sir If T' accept <M,w,0> it means M does not halt on w how ?

let say 00011...-0101-0 is encoding of L0 that mean string 0101 halt TM 00011...now when we design T' for L'(complement) then how can we certain that same encoding of TM 00011 does not halt on string 0101 ? is it because both <M,w,0> and <M,w,1> are different and no common string or some other reasoning ?

---

I'm confused there.. They have not used "third component i i  is a bit" anywhere !

WHen I read a question, it seems to me that i is irrelevant to this questino. They have not said, i is last bit of input of anything.

---

Sir,

Another alternative reasoning I think of is L0 can be thought of as recursive language i.e it halts on every input so decidable and L1 is undecidable and not even semi-decidable therefore it is not even R.E hence union of both will lead to language which is not decidable therefore it is not R.E and its complement is also not R.E.

is this reasoning correct ?

---

@Akash 

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

What is the input here? It is the description of a turing machine M, followed by the input to M "w" followed by 0. This is clear from the question. You can take this like a function with three arguments where the last one is a bit with value 0. 

@Abhishek You are completely off here. First point. It is not given that TM for L is halting for all inputs. It is given that input to a TM is another TM which must halt for all inputs. Secondly, union of an undecidable language and a decidable language can be decidable and even regular. For example, $\Sigma^*$ is regular and its union with any language results in a regular language. This discussion might be useful to you to skim through

https://docs.google.com/document/d/1F-JmRacHLMgszvfqmvR8PiEsSxhLXNdy2p8GTn7gUZI/edit

---

well explained sir

---

Thanks sir.very well explained got it in the first read !

---

If turing machine for L accept both <M,w,0> and <M,w,1> then for same string "w" turing machine halts and doesn't halt.WHAT DOES IT MEAN??

---

Arjun Sir-  is L0 recursively enumerable language?.  Similarly ,is L1 RE?

---

@arjun sir  A language that halts on tuning machine is recursive language and thats doesnot halt on tuning machine is recursive enumerable ... right ?

& we know a recursive language is subset of  recursive enumerable , their union must be recusrive enumerable as its REL is closed under union operation  and we cant predict predict about REL complement ?

sir ?correct me

---

A language that halts on tuning machine is recursive language and thats doesnot halt on tuning machine is recursive enumerable ..

TM for a recursive language always halt. But saying TM for a r.e. language does not halt is clearly wrong. Saying "may or may not halt" is also not technically correct. It should be "TM for a r.e. language always halt for any string in the language but may or may not halt (in reject state) for any string not in language).

Other things you told is correct- but not particularly useful for this question as since the languages are given, we cannot use the general properties of language classes. For example, removing the last bits of L0 and L1 makes their union regular set.

(This is one of the toughest question asked in this subject).

---

yup right sir ... but sir am still confused with the answer ... D not getting plz short explaination why L is not REL

---

L={<M,w>∣M halts on w}

Sir is this language R.E. ?

---

@Rajendra that is the Halting Problem ans it is r.e. but not recursive.

@Priyanka Did you get the answer for <M,w> - i.e., without the last bit included? The given question can only be answered via reduction as given above- so it cannot be made simpler- though if you get familiar with such questions answer can be guessed correctly in GATE.

---

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

---

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

---

@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 

https://www.youtube.com/watch?v=8TuLr0cggMY&list=PL601FC994BDD963E4&index=87&pbjreload=10 

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

---

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

 

---

Please help me with these 2 statements :

1] Union of 2 non-RE can be RE too,

I believe that the union of 2 RE would be strictly RE.

2] If L is NOT RE then L’ can be RE,

here I believe that L’ would also be non-RE.

https://cs.stackexchange.com/questions/80892/union-of-r-e-and-non-r-e-language

https://cs.stackexchange.com/questions/45826/undecidable-problem-and-its-negation-is-undecidable

---

I saw this explanation on cs.stackexchange. Can someone pls confirm if its correct:

https://cs.stackexchange.com/questions/119803/union-of-halting-like-problem-and-non-halting-like-problem

Discussion under the answer is worth reading too.

---

@Axl743 yes, that's correct and precisely explained.

Answer 2

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.

Comments

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.

Answer 3

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

Comments

You should watch this playlist

https://www.youtube.com/watch?v=FeT7iohSsPA&list=PL6aB9AKiIjgt1M4mSSiF2_wZGeJkaxlbQ

---

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

---

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

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

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

Answer 4

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.