Probando la indecidibilidad para un idioma que contiene cadena con cierta sintaxis.

Question

Digamos que tenemos el siguiente problema:

$$ \ mathcal {l} _1={\ langle \ mathcal {m} \ rangle |\ mathcal {m} \ \ texto {es una máquina de Turing y $ \ mathcal {l} (\ mathcal {m}) $ contiene una cadena con exactamente tres ceros} \} $$

Nos gustaría demostrar que $ \ mathcal {l} _1 $ no es decidible.Generalmente, usaría el teorema de Rice para demostrar que un idioma no es decidible, pero en el presente caso, no estamos tratando con una propiedad semántica del idioma, sino su sintaxis.En los casos en que tenemos que demostrar que se basan en la construcción del idioma, ¿cómo se vería el proceso y difiere de demostrar con el teorema de arroz?

Answer 1

Se puede pensar en una propiedad semántica del idioma, y su ok para usar el teorema de arroz aquí.

Define $ c={l | \ texto {Hay una cadena con exactamente 3 ceros en} l \} $

Entonces, $ l_1={ | m \ texto {es una máquina de Turing y} L (M) \ en C \} $ y porque $ C \ NEQ \ STOPSET $ y $ C $ no es todos los idiomas, entonces por el teorema de Rice, $ l_1 \ Notin R $ .