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$ 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

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$.


$\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?).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.