Provotant une indécidabilité pour une langue contenant une chaîne avec certaines syntaxes

Question

permet de dire que nous avons le problème suivant:

$$ \ mathcal {l} _1={\ lger \ mathcal {m} \ Range |\ mathcal {m} \ \ \ \ est une machine de Turing et $ \ mathcal {l} (\ mathcal {m}) contient une chaîne avec exactement trois zéros} \} $$

Nous aimerions prouver que $ \ mathcal {l} _1 $ est indécitable.J'utiliserais généralement le théorème de Riz pour prouver qu'une langue est indécidable, mais en l'espèce, nous ne traitons pas d'une propriété sémantique de la langue, mais plutôt de sa syntaxe.Dans les cas où nous devons prouver en fonction de la construction de la langue, comment le processus ressemblerait-il et diffère de prouver avec le théorème de Riz?

Answer 1

On peut penser qu'une propriété sémantique de la langue et son OK utiliser le théorème de Rice ici.

Définir $ c={l | \ text {Il y a une chaîne avec exactement 3 zéros in} l \} $

donc, $ l_1=\ { | m \ texte {est une machine Turing et} l (m) \ in c \} $ et parce que $ c \ neq \ videtyset $ et $ C $ n'est pas toutes les langues, puis par le théorème de Rice, $ l_1 \ notin r $ .