# Is the language of all TMs accepting all strings starting with 010 decidable?

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.

• Your language is unfortunately not decidable. Nov 10, 2018 at 18:20
• Hi could you please elaborate on that? What makes that language undecidable? Thanks! Nov 10, 2018 at 18:31
• It's your exercise. Nov 10, 2018 at 18:31
• 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. Nov 10, 2018 at 18:36
• 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. Nov 10, 2018 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 $$\qquadL(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?).