turing machine

Question

Comments

quetion is for set of all tiring machine which is infinite ryt if some machine go for loop you have to wait for that na , so you can not even say yes.

---

Why it will go in in a loop ...it is said that a turing machine that accpets atleast one language...

---

@Habib yes, that is quite common as no where it is mentioned clearly. Actually some undecidable problems are semi-decidable. In fact anything that is not "decidable" is "undecidable". So, rec = decidable, r.e. = semi-decidable, not r.e. = not even semi-decidable.

Answer 1

$L = \left \{ Set\ of\ all\ TM\ that\ accept\ atleast\ one\ string\right \}$

Well, If such a string is there, then we simply run that input on TM. If that input is in the language of TM, it will accept and halt.

No need to check further strings.

But, what if there is no such string and we ran many inputs by dovetailing on this TM but it is not accepting anything. Then, how can we be sure that TM accepts atleast 1 string. 

So, we can confirm the YES case but we are not sure about the NO case.

Hence, the language L is RE and we can designa recognizer for this .

---

Rice theorem is pretty good for such questions as it is talking about the property of language of TM's.

According to the Rice theorem, it is undecidable. How?

It is a non trivial property because there are TM which do accept atleast 1 string and there are TM which even not accept even 1.

(In this world, do all TM accept atleast 1 string . If you say yes, then this is a trivial(always true) property otherwise it is non trivial)

Hence, Tyes can be any TM which accepts at least 1 string and Tno can be any TM which doesn’t even accept 1 string.

Comments

@kapil

for property to be non trivial we can say T _{yes =}∑*    and T_no =∅ rt ??

---

For property to be non trivial, we just have to show that some TM follow that P and some don't. Rice theorem is only used to show UD.

---

yes kapil Rice theorem is only used to show UD. but actually i am trying to understand rice theorem so tell in my above comment whether i am wrong or correct . thanks

---

Kapil,what about RE ot NOT RE classification?Is it semi decidable or fully undecidable?We cant apply 2nd part i guess

---

He already showed that it is R.E. And this means that we can NEVER show that the property is non-monotonic and hence Rice's second theorem can't be applied.

---

@ Arjun Sir if Rice's second theorem is not applicable then can we say for sure that it is RE???

---

No never. Rice's theorem part 2 is one way only like pumping lemma. Actually unless a theorem has "if and only if" like Myhill Nerode theorem it should always be one way. But Rice's theorem part 1 is two way because it talks about "non-trivial" properties and if a property is "trivial" it means it is already decided. But most GATE people do not even think what is trivial and just write what they have seen in notes or heard from their teacher's mouth.

$L = \{\langle M \rangle \mid L(M) = \Sigma^* \}$

here, we cannot apply Rice's theorem part 2, but still $L$ is not even r.e.

---

Thank you sir. But why is this L not RE??

---

You can see here - one of the oldest question on this site :)

https://gateoverflow.in/79/l-m-%CF%83

---

Got it sir,I was not able to apply second part,so i was just confirming.
I got the habib's logic of complementary problem,that seems a better way to apply if second part not applicable(provided we know what complement is exactly):)

---

Yes, that is pretty good logic and should be used wherever possible. But won't work in the question in my above comment as both $L$ and $L'$ are not r.e.