0
$\begingroup$

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?

Improve this question
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you explain what exactly is $R$ in your answer? $\endgroup$ – C. R. Jun 11 '20 at 9:51
  • $\begingroup$ it is the set of recursive languages . i.e, all decidable languages. en.wikipedia.org/wiki/Recursive_language $\endgroup$ – nir shahar Jun 11 '20 at 10:02
  • $\begingroup$ Its a pretty standard notion. Used pretty much everywhere to denote decidable languages $\endgroup$ – nir shahar Jun 11 '20 at 10:03

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.