Provando indecidenciar uma linguagem que contém string com determinada sintaxe

Question

permite que temos o seguinte problema:

$$ \ mathcal {l} _1= {\ langle \ mathcal {m} \ rangle |\ mathcal {m} \ \ text {é uma máquina de Turing e $ \ mathcal {l} (\ mathcal {m}) $ contém uma string com exatamente três zeros}} $$

Gostaríamos de provar que $ \ mathcal {l} _1 $ é indecidível.Eu geralmente usaria o teorema de arroz para provar que uma linguagem é indecida, mas no presente caso, não estamos lidando com uma propriedade semântica da linguagem, mas sim sua sintaxe.Nos casos em que temos que provar com base na construção da linguagem, como seria o processo e diferiria de provar com o teorema de arroz?

Answer 1

Pode ser considerado uma propriedade semântica da linguagem, e é ok para usar o teorema de arroz aqui.

Definir $ c= {L | \ text {Há uma string com exatamente 3 zeros em} l \} $

Então, $ l_1= { | m \ text {é uma máquina de Turing e} l (m) \ em c \} $ e porque $ c \ neq \ vazio $ e $ c $ não é todo idioma, então pelo teorema de arroz, $ l_1 \ notin R $ .