Question

L={⟨M⟩|TM accepts exactly 154 strings}

--------------------------------------------------------------------------------------------------------

this language is not decidable but is this R.E??

by second rice theorem, T_{yes =}{154 strings} and T_no = more than 154 strings

hence, Tyes is subset of Tno.so,it is not even R.E.

am i right?

please correct me.

Answer 1

$T_{yes} = \big \{ 1,10,100,1000, \dots, 154\;times \big \}$, but if you can come up with atleast one $T_{no}$, it can be said that it is not a trivial property and language is undecidable.

$T_{no_1} = \sum^*$

$T_{no_2} = \big \{1, 10 \big \}$

$T_{no_3} = \big \{1, 10, 100, 1000, \dots, 156\;strings \big \}$ (example you took)

So, We can say it is not even recursively enumerable if we can comeup with atleast one $T_{yes}$ and $T_{no}$ such that $T_{yes} \subset T_{no}$

According to your example, $T_{yes} \subset T_{no}$, So, it is sufficient to say that it is not even R.E.

Comments

typo  Corrected:)

---

thanks a lot :-)

---

@Debashish wt is rice extended theorem ??