Decidability

Question

Consider the following language over $\sum=\{0,1\}$

$L=\{<M>|$ M is a turing machine that accepts all strings of length atmost 5 $\}$

Since, this is a non-trivial property of TM, so surely it is undecidable.

Now, Applying Rice’s Theorem part 2, $T_{yes}=\{0,1\}$ and $T_{no}=\sum^*$ and $T_{yes} \subset T_{no}$ so this is NOT RE.

Have I correctly applied property 2?

Comments

Even I think like this, don't know if that's the correct way!

---

Since it is the property of Turing Machine and not that of Recursively Enumerable language, I think we can't apply Rice's theorem here. However We can say “no” is M accepts some string, but can we every say “yes” as we need to check infinite number of strings. So it is not Recursively Enumerable. Correct me if I am wrong.

Refer slide 23 https://gateoverflow.in/?qa=blob&qa_blobid=13695039841867827427

---

We can say no when any string is rejected.

We can say yes when M accepts all strings of length 0 to 5. But we cannot determine this as for a string M will halt or not is not known. Hence, undecidable I think.

---

@Aarvi Chawla-No, it is about Language accepted by a turing machine.Here I am not talking about how many states machine M has, or whether it ever makes a left move.Here I am talking about what strings it accepts.So, I can apply Rice's theorem.

---

@Ayush Upadhyaya @gauravkc

Isn't the problem semi-decidable?

As in, the strings which have length atmost 5 are finite. We can list them out. Now all these strings can be inputted to the given TM using dovetailing method. If the TM really accepts all the given strings, we can say yes. If it goes into a loop, we may not be able to say anything. So at least for the yes part, we'll be able to say, isn't it?

---

@Ayush Upadhyaya

I think the part 2 is applied incorrectly as your $T_{no}$ = $\sum^{*}$ also satisfies the given language.

The question is that TM accepts all strings which have length atmost 5. It may or may not accept strings of other lengths which is of no concern to us.

If the question would have been that the TM accepts only strings having length atmost 5 then it would be not RE.

 

---

@Fyse exactly

---

@Fyse Oh Yes. We can say yes. Thanks :)

---

@Fyse-Thanks.Got it :)