Hier ist mein Ansatz: Ich werde zeigen, dass Sie, wenn Sie Ihr Problem entscheiden können, das Korrespondenzproblem (PCP) von Post entscheiden können , das bekanntermaßen nicht entscheidbar ist.
Denken Sie daran, PCP ist ein Entscheidungsproblem, bei dem gefragt wird, ob Sie in einer Menge von Tupeln eine Sequenz (inkl. Wiederholung) erstellen können, so dass die verkettete s und die verketteten s dieser Sequenz bilden dasselbe Wort. Beachten Sie, dass das Alphabet mindestens 2 Zeichen haben muss.2P={(x1,y1),…,(xn,yn)}xiyi
Sei also eine Instanz des PCP. Betrachten Sie die folgende kontextfreie Grammatik, in der wir ein neues Terminalsymbol für das te Element in . Die Grammatik hat die folgenden Regeln:
(Die Variable ist nur dazu da, auszuschließen ).PtiiS eingeführt habenP X'S⇒!
SXX′Y→X!Y→x1X′t1∣x2X′t2∣⋯xnX′tn→x1X′t1∣x2X′t2∣⋯xnX′tn∣ε→y1Yt1∣y2Yt2∣⋯ynYtn∣ε
X′S⇒!
Natürlich können wir bei jeder Grammatik einen entsprechenden PDA finden, der dieselbe Sprache wie die Grammatik akzeptiert. Konstruieren Sie also den entsprechenden PDA und verwenden Sie dann den hypothetischen Algorithmus für Ihr Problem, um zu bestimmen, ob dieser PDA ein Wort der Form akzeptiert (dh ob man aus dieser Grammatik ein Wort der Form ableiten kann ). Ich werde zeigen, wie diese Informationen verwendet werden, um die PCP-Instanz zu lösen .u ! v P.u!vu!vP
Nehmen wir jetzt an, dass ein Wort in dieser Grammatik ist. Das Wort besteht aus zwei Teilen, dem Suffix, das aus den Terminals besteht, und dem Rest, der als Präfix bezeichnet wird. Gleiches gilt für . Wir haben genau dann, wenn ihre Präfixe und Suffixe übereinstimmen. Die Suffixe stimmen nur überein, wenn wir dieselbe Folge von Tupeln aus , um die Wörter und . Die Präfixe von und stimmen überein, wenn die Verkettung der s und s (basierend auf der durch die s gegebenen umgekehrten ) dieselbe ist. Daheru t i v u = v P u v u v x i y i t i u = v P.u!vutivu=vPuvuvxiyitiu=v genau dann, wenn es eine Lösung für die PCP-Instanz .P
Wenn es eine Lösung für die PCP-Instanz gibt, ist es ähnlich, aus der Lösung ein Wort der Form zu konstruieren , das von dieser Grammatik abgeleitet werden kann.u ! vPu!v
Daraus folgt, dass die PCP-Instanz genau dann eine Lösung hat, wenn diese Grammatik ein Wort der Form . Wenn es einen Algorithmus zur Entscheidung Ihres Problems gäbe, könnten wir ihn zur Lösung von PCP verwenden. Aber natürlich ist PCP als unentscheidbar bekannt, daher ist auch Ihr Problem unentscheidbar.u ! vPu!v
Der Ansatz könnte wie folgt sein. Versuchen Sie, eine kontextfreie Sprache (= PDA) zu erstellen, die die Berechnungsschritte eines TM codiert, sodass die vollständige Berechnung erfolgreich ist, wenn ein Wort der von Ihnen beschriebenen Form vorhanden ist.
Zuerst müssen Sie separate Konfigurationen codieren: Bandinhalt + Status + Positionskopf (Sie haben dies für die Grammatikäquivalenz gesehen). Eine kontextfreie Sprache kann einen einzelnen Schritt einer Berechnung codieren, vorausgesetzt, Sie verwenden das Spiegelbild C # m ( C ' ) , wobei m ( C ) das Spiegelbild (Umkehrung) von $$ C $ bezeichnet. (Ich bin hier schlampig: Möglicherweise müssen Sie die Konfiguration und ihre Beschreibung unterscheiden.)C⊢C′ C#m(C′) m(C)
Betrachten Sie nun die Sprache der einzelnen Schritte, die mit der Sprache der doppelten Konfigurationen : mit für jedes , . Dies ist kontextfrei, zusätzlich Code als Anfang und als endgültige Konfiguration.C0#C1#m(C2)#C3#m(C4)#…C2n−1#m(C2n)#Cf! C′1#m(C′1)#C′2#m(C′2)#…C′n+1#m(C′n+1) k C2k−1⊢(C2k) C0 Cf
Jetzt stellt der erste Teil sicher, dass wir aufeinanderfolgende Schritte haben, der zweite Teil, dass aufeinanderfolgende Konfigurationen gleich sind. Wenn beide Teile übereinstimmen, haben wir eine Berechnung. Was wir nicht entscheiden können.
Das ist die Idee. Möglicherweise sind einige Indizes falsch, und die gesamte Sequenz muss binär codiert werden, aber das kann gelöst werden.
quelle