I am trying to figure out if this language is decidable: $$ \{ \langle M \rangle \mid \text{$M$ accepts all strings starting with 010}\}. $$
My intuition is that it is. Whatever string $w$ starts with 010 it accepts, and if it doesn't it rejects.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Your language is unfortunately not decidable. $\endgroup$ – Yuval Filmus Nov 10 '18 at 18:20
-
$\begingroup$ Hi could you please elaborate on that? What makes that language undecidable? Thanks! $\endgroup$ – jPrime Nov 10 '18 at 18:31
-
$\begingroup$ It's your exercise. $\endgroup$ – Yuval Filmus Nov 10 '18 at 18:31
-
$\begingroup$ You seem to be misunderstanding the question, though. The task is to decide whether a given TM accepts all strings starting with 010. It is not to accept all strings starting with 010. The input is a TM, not a string. $\endgroup$ – Yuval Filmus Nov 10 '18 at 18:36
-
$\begingroup$ I see. Thank you very much. Your answer clears it a lot! I actually think using Rice's theorem helped me understand better your reply. $\endgroup$ – jPrime Nov 10 '18 at 19:01
Add a comment
|
$\begingroup$
$\endgroup$
According to $Rice's$ $theorem$,
$\qquad$ $L$ = { $\langle M \rangle$ | $L (M) ∈ P$ } is undecidable if $P$ is a non-trivial semantic property of $\qquad$$L(M)$.
$\qquad$ P is the set of all languages that satisfies a particular property
If the following two properties hold, it is proved as undecidable −
Property 1 (Semantic) − If $M_1$ and $M_2$ recognize the same language, then either $\qquad$$\qquad$$\langle M_1 \rangle ,\langle M_2\rangle \in L$ or $\langle M_1 \rangle ,\langle M_2\rangle \notin L$.
Property 2 (Non-trivial) − There exists $M_1$ and $M_2$ such that $\langle M_1 \rangle \notin L$ and $\langle M_2 \rangle \notin L$.
Now,
$\quad$ 1) For any two TMs, $M_1$ and $M_2$ with $L(M_1) = L(M_2)$ either both $M_1$ and $M_2$ both accept all strings starting with 010 or both don't accept.
$\quad$ 2) There exists TMs that accepts strings starting with 010 and not accepting strings that starts with 010.
Therefore, the property of the language of a TM to start with 010 is a semantic and non-trivial. Hence, according to Rice's theorem, the given language is undecidable.
$L$ is recognizable as TMs that accepts when given as input strings starting with 010 always accepts and halts. But complement of $L$ isn't recognizable as both $L$ and complement of $L$ being recognizable will mean that $L$ is decidable(why?).
