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$ Nov 10, 2018 at 18:20
  • $\begingroup$ Hi could you please elaborate on that? What makes that language undecidable? Thanks! $\endgroup$
    – jPrime
    Nov 10, 2018 at 18:31
  • $\begingroup$ It's your exercise. $\endgroup$ Nov 10, 2018 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$ Nov 10, 2018 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, 2018 at 19:01

1 Answer 1


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 and acknowledge you have read our privacy policy.

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