Warum ist die folgende Sprache unentscheidbar?

Question

Ich lerne gerade für meine Prüfungen in diesem Semester und habe versucht, einige alte Prüfungen aus den letzten Jahren zu lösen.

Die Frage besteht darin, zu zeigen, dass L unentscheidbar ist.$L=\{w|T(M_w) eq\emptyset \land \forall x \in T(M_w):xx\in T(M_w)\land xxx otin T(M_w)\}$

Ich habe gezeigt, dass die Sprache $ L '= {W | T (m_w) neq leerseet } $ ist aufgrund des Rice-Theorems unentscheidbar.Ich habe Turing-Maschinen erstellt $M_1$ mit $T(M_1)=\emptyset$ Und $M_2$ mit $T(M_2)=\Sigma^*$ um zu zeigen, dass die Sprache L' nicht trivial ist.(seit $1\in L$ Und $2 otin A$.Ohne Beschränkung der Allgemeinheit gehe ich davon aus, dass diese Maschinen die Gödelindizes 1 und 2 haben)

Mein Problem ist nun, dass ich keine Möglichkeit weiß zu zeigen, dass dieses Ergebnis auf die Sprache L übertragen werden kann.Ich weiß, dass die Sprache L nur solche Gödel-Indizes enthalten darf, dass für diese Indizes das folgende TM unendliche Wörter akzeptieren muss (denn im Fall von $x\in T(M_w)$ da muss sein $xx\in T(M_w)$...und deshalb muss es sein $xxxx\in T(M_w)$ usw.)

Ich würde mich über Anregungen/Antworten freuen!Dank im Voraus

Answer 1

Dies ist eine direkte Folge des Rice-Theorems.Ein Wort $w$ ist in $L$ Wenn $T(M_w)$ erfüllt die folgende semantische Eigenschaft:

$T(M_w)$ ist nicht leer und für jeden $x \in T(M_w)$, wir haben $x^2 ​​\in T(M_w)$ Und $x^3 otin T(M_w)$.

Um zu zeigen, dass diese Sprache gemäß dem Rice-Theorem unentscheidbar ist, müssen wir zwei Turing-Maschinen zeigen $w_1$ Und $w_2$:eine, die die Eigenschaft nicht erfüllt, und eine andere, die sie erfüllt.Wir können nehmen $w_1$ eine solche Maschine sein $T(M_{w_1}) = \emptyset$, Und $w_2$ eine solche Maschine sein $T(M_{w_2}) = \{ a^{2^n} :n \geq 0 \}$.