Dimostrando l'indecididabilità per una lingua che contiene stringa con una certa sintassi

Question

Diciamo che abbiamo il seguente problema:

$$ \ Mathcal {l} _1={\ Langle \ Mathcal {m} \ Rangle |\ Mathcal {m} \ \ text {è una macchina di Turing e $ \ mathcal {l} (\ mathcal {m}) $ contiene una stringa con esattamente tre zeri} \} $$

Vorremmo dimostrare che $ \ Mathcal {l} _1 $ è undecidable.Generalmente userei il teorema del riso per dimostrare che una lingua è indecidabile, ma nel caso di specie, non ci occupiamo di una proprietà semantica della lingua, ma piuttosto la sua sintassi.Nei casi in cui dobbiamo dimostrare in base alla costruzione della lingua, come sembrerebbe il processo e differire dal dimostrare con il teorema del riso?

Answer 1

Può essere pensato a una proprietà semantica della lingua, e il suo OK per usare il teorema del riso qui.

Definisci $ c={l | \ text {c'è una stringa con esattamente 3 zeri in} l \} $

SO, $ l_1={ | m \ text {è una macchina Turing e} l (m) \ in c \} $ e perché $ c \ neq \ vuoto $ e $ c $ non è ogni lingua, quindi con il teorema del riso, $ l_1 \ NOTIN R $ .