Proving undecidability for a language which contains string with certain syntax
-
29-09-2020 - |
Question
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?
Solution
It can be thought of a semantic property of the language, and its ok to use Rice's theorem here.
Define $C=\{L|\text{there is a string with exactly 3 zeros in }L\}$
So, $L_1=\{<M>|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$.