Unbeweisbarkeit für eine Sprache, die eine Zeichenfolge mit bestimmter Syntax enthält

Question

lassen Sie sagen, wir haben das folgende Problem:

$$ \ Mathcal {l} _1={\ langle \ matcal {m} \ rangle |\ mathcal {m} \ \ text {ist eine Turing-Maschine und $ \ Mathcal {l} (\ mathcal {m}) $ enthält eine Zeichenfolge mit genau drei Zeros} \} $$

Wir möchten beweisen, dass $ \ Mathcal {l} _1 $ unentschlossen ist.Ich würde im Allgemeinen den Satz von RICE verwenden, um zu beweisen, dass eine Sprache unentscheidbar ist, aber im vorliegenden Fall handelt es uns nicht um ein semantisches Eigentum der Sprache, sondern seine Syntax.In Fällen, in denen wir basierend auf der Konstruktion der Sprache nachweisen müssen, wie würde der Prozess aussehen und sich von der Beweis von RICE-Satz unterscheiden?

Answer 1

Es kann an ein semantisches Eigentum der Sprache gedacht werden, und sein ok , um Rice's theorem hier zu verwenden.

Definieren Sie $ C={l | {Text {Es gibt eine Zeichenfolge mit genau 3 Zeros in} l \} $

so, $ l_1={ | m \ text {ist eine Turing-Maschine und} l (m) \ in c \} $ und weil $ c \ neq \ emesyetet $ und $ C $ ist nicht jede Sprache, dann von Rice's Theorem, $ l_1 \ NOTIN R $ .