# Proving undecidability for a language which contains string with certain syntax

Lets say we have the following problem:

$$\mathcal{L}_1 = \{\langle \mathcal{M} \rangle | \mathcal{M}\ \text{is a Turing machine and \mathcal{L}(\mathcal{M}) contains a string with exactly three zeros}\}$$

We would like to prove that $$\mathcal{L}_1$$ is undecidable. I would generally use Rice's theorem to prove that a language is undecidable, but in the present case, we aren't dealing with a semantic property of the language but rather its syntax. In cases where we have to prove based on the language's construction, how would the process look like and differ from proving with Rice's theorem?

Define $$C=\{L|\text{there is a string with exactly 3 zeros in }L\}$$
So, $$L_1=\{|M \text{ is a turing machine and } L(M)\in C\}$$ and because $$C\neq\emptyset$$ and $$C$$ is not every language, then by Rice's theorem, $$L_1\notin R$$.
• Could you explain what exactly is $R$ in your answer? Jun 11 '20 at 9:51