Question

Which of the following languages are Recursively Enumerable language?

• A. $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$
• B. $\{\langle M \rangle \mid M \text{ is a TM and }L(M) = \{00, 11\} \}$
• C. $\{ \langle M1, M2, M3 \rangle \mid L(M1) = L(M2) \cup L(M3) \}$
• D. All of these

Comments

wts the ans i think none of above is correct.??

---

Nopes.. that's not even in options :)

---

should be a...

---

I am not able to understand why equivalence of two TM's are not even semi decidable. Someone may explain me.

Answer 1

a) is recursively enumerable but not recursive. If there is such an input, then we can say "yes". But for the no case we cannot decide as we can never be sure that such an input does not exist.

b) is not RE. We can use Rice's 2nd theorem which will be most straightforward. Here we are given the encoding of a TM and asked if the language of that machine is {00, 11}. (This is different from asking if that machine accepts 00 and 11, which would be RE). So, now to apply Rice's 2nd theorem, we need to make 2 TMs, TM_yes and TM_no, with L(TM_yes) = {00,11} and L(TM_no) != {00,11} and L(TM_yes) subset of L(TM_no). (The last condition is for non-monotonicity). 
Here, we can easily get a TM_no as L(TM_no) can be {00, 11, 011} or any subset of sigma star containing {00, 11} except {00, 11}. Since we get TM_yes, and TM_no, the given language is not RE. 

c) Checking the equivalence of language of 2 TMs itself is not even semi-decidable. So, this is clearly a non-recursively enumerable language as we can easily reduce TM equivalence problem to this by taking $L(M_3) = \phi.$

Comments

@Arjun Sir hats off :) mind == blown, nice explanation .

---

Thanks :)

---

Arjun sir plz explain the (b) part,,i m not getting it.

---

The b part makes use of Rice's theorem. It is very useful to solve problems like these. 

http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples

---

Why have you not applied Rice's 2^nd Theorem in Option 1.

T_yes = ∅

T_no = Σ^∗ and T_yes ⊂ T_no. 

_{It is making the language as not r.e.} 

---

Tno is wrong here- it also contains strings of length < 100 in it. Here, Tyes and Tno are mutually exclusive- no intersection. So, subset relation cannot hold.

---

@Arjun Sir ,  How aditya can take T_yes = ∅ . At least it shud contain some string whose length is less than 100.  ??

---

Yes, that Tyes is not valid. Tyes can be $\{\epsilon\}$ but not $\{\}$.

---

sir, TMs can  accept {∈} ?? I think Tape must contain some alphabet symbol .

---

If the first read symbol is 'b'- the blank symbol, and TM move to an accept state, that means it accepted $\epsilon$.

---

sir ,

In option (b)  language of the turing machine is finite so it is decidable but why we are going for rice second theorem                    

L={<M>, M is TM and TM is decidable(turing decidable) }

then L is recursive or not?

---

A is REC  because The number of possible inputs is finite, and the number of steps M runs on each input is finite, therefore M is guaranteed to halt and decide the language"

I will have finite number of strings of length at most 100 ( because there is no use of taking strings of more than 100 machine will not definitely halt on them in 100 steps).

now I will execute each TM which is provided as an input for 100 steps and if there is at least one string on which TM halts in 100 steps that TM will belong to our language.

Hence Language A is decidable because Machine needs to run for finite number of steps on finite number of inputs.

---

@Venkat

In option (b)  language of the turing machine is finite so it is decidable but why we are going for rice second theorem                   

What is "it" here?

@Vijay

now I will execute each TM which is provided as an input for 100 steps and if there is at least one string on which TM halts in 100 steps that TM will belong to our language.

What if you do not get any such string? After how many steps will you stop the algorithm and say "no"?

---

yes sir right...input length is less than 100 dosent means TM will halt if it would have been TM which halt swithin 100 steps then it was Recursive ....accepting languages is not enough we have to reject also then only we can say TM halts

---

@Arjun, yes I misiterpreted the problem, later i got it.

---

it means the language is finite

---

The question is for "checking" if the language is so. The language describing this problem is not finite.

---

@Arjun sir

L={<M>, M is TM and TM is decidable(turing decidable) }

then L is recursive or not?

---

No. L is not recursive. L contains description of TMs, whose language is recursive.

---

@arjun sir, do you mean that L here, is the collection of all such encodings of Turing machines for which the above property holds? Turing machines can be encoded and enumerated anyhow.. Please clarify

---

@arjun sir,i did nt get the reason for part A.

as there can be infinite number of strings of length < 100.are we gona check each one of them one by one??what if no one halts??

is it R.E because of finite length??

why is it not recursive??

---

@arjun sir,how part A and this statement is different ----

. {⟨M⟩ | M is a TM and there exists an input which halts within 100 steps}

please explain..

---

it can not be recursive as we are not sure whether it will reject or loop forever for those strings having length greater than 100 if we are sure about those inputs then it would be recursive

---

there exist an input for which  turing machine halts within k steps now no of inputs up to length 100 would be finite when we simulate those inputs on turing machine it will not process them more than 100 steps in any case those inputs will halt in any case within 100 steps now for inputs having more than 100 length they are going to take more than 100 steps definitely this decide the problem as we are sure about yes and no cases therefore recursive here

---

put more stress within k steps in that problem and look at that perspective

---

@Arjun sir,can you please tell how can we apply Rice's Theorem on the c part,when there are three Machines M1,M2,M3.Do we need to consider 3 machines satisfying Tyes and 3 machine satisfying Tno?How will we satisfy non monotone property here?Please help

---

@Arjun sir, Please clear my doubt above:(?

---

@Rahul No, that is not possible; that statement was wrong. I have corrected it now.

---

Thanks sir.In the updated point(iii),you mentioned:-

 

 we can easily reduce TM equivalence problem to this by taking L(M3)=ϕ.

Here,have we reduced TM equivalence to this problem(iii) , or our problem(iii) to TM equivalence?

---

yes, it is "TM equivalence problem to our problem". Given TM equivalence problem we just added one $M_3$ extra and made it to our given problem. Now, if we solve our problem - we solved TM equivalence problem. (We cannot say we solved our problem if someone solves TM equivalence problem).

---

@Arjun sir,

For first option is following approach correct ?

As here in this case its not easy to find Tyes and Tno so instead of going for rice theroem we can prove language RE or not if there is enumeration method such that TM halts and say yes on all YES instances but may not for NO instance

So we have a UTM for Language in L which is set of TMs

We give each TM to UTM to check whether that TM belongs to language or not ?

Now each of such TM is given inputs of length less than 100 one by one , but problem arises if that TM doesn't accept string then no further checking can happen so , inputs are given to TM in dovetailing fashion.

Hence Machine will definitely halts and say yes if there exists such string but may not if no such string.

Hence we found that for Language L there exists a TM i.e UTM which halts on all YES instance but may not for NO instances Hence Language is RE but not REC

---

@Arjun sir

How is "language of a TM" different from "if the TM accepts 00,11" ??

As mentioned in the explanation of sub-part B.

Here we are given the encoding of a TM and asked if the language of that machine is {00, 11}. (This is different from asking if that machine accepts 00 and 11, which would be RE).

Is it that in the first case we have to check whether the TM just accepts {00,11} but in the later case we have to check whether the TM accepts 00,11 or any other input?