MadeEasy Test Series: Theory Of Computation - Decidability

Question

Consider the following languages

A={<M>|M is a TM and |L(M)| >= 3}

B={<M>|M is a TM that accepts some string}

Which of the following is correct?

(a.) A is decidable, B is partially decidable

(b.) A is partially decidable, B is decidable

(c.) Both A and B are decidable

(d.) Both A and B are partially decidable

 

Answer given : (d.)

But how?

Answer 1

A. Language of Turing machine contains at least 3 strings.

B. Language of Turing machine contains at least 1 string.

Both are non-trivial property of r.e. languages and hence undecidable as per Rice's theorem. Now, for semi decidability (answering for yes cases) of A, we can feed the Turing machine strings from $L$ one by one (using dovetailing technique to avoid any infinite loop for some string) and as long as the language is sure to contain at least 3 strings, it will eventually accept 3 distinct strings and we can stop. (If there are no such 3 strings, this technique goes to infinite loop and that is why we cannot completely decide this).  For B also do the same technique using replacing 3 with 1.

So, D choice.

Comments

Thank you Sir. Rice theorem is new for me. From where to study it?

---

For $L_1$,$ T_{yes} = $ {1,11,111} and $T_{no} =$ {1}, but $T_y$ is not a subset of  $T_n$. So we cannot apply rice theorem. How to proceed next??

Is this approach wrong.

---

plzz see ans given by arjun sir carefully
nd u r right rice 2nd  thm does nt apply here....

---

@abcd2 actually not enough. Just one $T_{yes}$ and $T_{no}$ is not enough to say Rice's second theorem is not applicable. We should show no such TMs exist- intuition is enough here.

Now, when Rice's theorem is not applicable we have only reduction left. But I believe it is quite tough for most bachelor level people. So, better way is to think about the problem and try to simulate the TM with a C program. When we know the problam and what it really means, 99% we get the exact answer in case of TM decidability.