turning machine

Question

TM 'M1'  accepts atmost 2 distinct input .

TM 'M2' accept more than 2 distinct input .

Which of the machine is Turning recognizable ?

Answer 1

1st Theorem of Rice Theorem says,

Any non-trivial property of the LANGUAGE recognizable by a Turing machine is undecidable

"TM 'M1'  accepts atmost 2 distinct input ."

What is non trivial here? Language having atmost 2 distinct strings.

Say L(TMyes)  =$\emptyset$ satisfies this.

L(TMno) can be any language of more than 2 strings.

So, from 1st theorem of Rice Theorem, we can say that the given problem is undecidable.

Now, Rice 2nd Theorem

"Any non-monotonic property of the LANGUAGE recognizable by a Turing machine is unrecognizable"

Say, TMyes=$\emptyset$ , TMno=$\Sigma ^*$,

Now, TMyes$\subset$TMno

So, 2nd Rice Theorem also satisfies here. So, it is not even TM recognizable

TM 'M2' accept more than 2 distinct input .
Here minimum no. of strings in L is 3. TMno can be $\emptyset$. So, It is TM undecidable.

Now, check 2nd theorem of TM.

Here we cannot get any $L(T_{yes})$ and $L(T_{no})$ such that $L(T_{yes}) \subset L(T_{no})$. So, this is not a non-monotonic property of recursively enumerable languages and hence Rice's second theorem is not applicable. But this does not mean that this language is Turing recognizable (Rice's second theorem is one way like Pumping lemma). But this language is indeed Turing recognizable as we can simulate the TM with inputs one by one and using dovetailing technique and we are eventually sure to catch the "3" distinct inputs which are accepted and sure to say "yes" for yes cases of the language (for "no" cases our TM never halts).

Reference http://gatecse.in/rices-theorem/#comment-1599

Comments

rice theorem link you gave contains this theory.

"One of these is recognizable, the other one is not.
Which one is which?
{M | L(M) contains at most 154 strings}
{M | L(M) contains at least 154 strings}
Is there a generic condition for unrecognizability?

Monotone Properties P
• L(M) is infinite
• L(M) = Σ*
• L(M) contains at least 154 strings
• L(M) contains 11111

“Every non-monotone semantic property
of Turing machines is unrecognizable”  "

does it contradict your answer or I din't get?

---

Now, check plz.

---

Here minimum input of TM will be 2. TMno=Σ∗. So, It is TM undecidable.

For  part ;- How can Σ∗ be Tno for this case?It will always accept more than two distinct characters?Can you check again. Σ∗ can be Tyes for this but will never be Tno.And turing machine which will say NO will never be proper superset of Tyes,so we cant use Rice;s part 2 ,hence it is recogonizable.Please correct if wrong

---

Can you plz reply to my comment?@sreshta?

---

We have to choose TM_no in such a way, that will be always superset of T_yes

---

TMno=Σ∗,but how can you say that this is Tno,it will always accept distinct input more than 2?

---

@Rahul That was wrong. Corrected now..