Доказательство неразрешенности для языка, который содержит строку с определенным синтаксисом

Question

Позвольте сказать, что у нас есть следующая проблема:

$$ \ mathcal {l} _1={\ lange \ mathcal {m} \ rangle |\ mathcal {m} \ \ text {представляет собой Turging Machine и $ \ mathcal {l} (\ mathcal {m}) $ содержит строку с ровно тремя нулями} \} $$

Мы хотели бы доказать, что $ \ mathcal {l} _1 $ неразрешен.Как правило, я бы вообще использовал теорему Риса, чтобы доказать, что язык неразрешен, но в настоящем деле мы не имеем дело с семантическим свойством языка, а скорее его синтаксис.В тех случаях, когда мы должны доказать, основываясь на строительстве языка, как бы этот процесс выглядел и отличается от доказательства с теоремой Риса?

Answer 1

Это можно подумать о семантическом свойстве языка, и его ok использовать теорему риса здесь.

Определите $ c={l | \ text {Есть строка с ровно 3 нуля в} l \} $

Итак, $ l_1={ | m \ text {представляет собой Turging Machine и} l (m) \ in c \} $ и потому, что $ c \ neq \ pertyset $ и $ C $ не каждый язык, затем по теореме Риса, $ l_1 \ notin r $ .