8.8 Anwendungen des Postschen Korrespondenzproblems

Erinnerin Sie sich an kontextfreie Grammatiken? Das waren formale Grammatiken wie zum Beispiel $\begin{aligned} S & \to T c \\ T & \to T a T b \\ T & \to ϵ \end{aligned}$ Diese Grammatiken erlauben uns, gewisse Sprachen zu beschreiben, indem Sie Regeln festlegen - hier Produktionen genannt, nach welchen man aus dem Startsymbol $S$ Wörter über dem Alphabet (hier: ${a, b, c}$ ) ableiten kann. Beispielsweise: $\begin{array}{r} S \Rightarrow T c \Rightarrow T a T b c \Rightarrow T a T a T b b c \Rightarrow T a T a b b c \Rightarrow T a a b b c \Rightarrow a a b b c \end{array}$ Kontextfreie Grammatiken werden zum Beispiel verwendet, um die Syntax von Dateiformaten, Programmiersprachen und manchmal sogar natürlicher Sprachen zu beschreiben. Es wäre daher schön, über gegebene kontextfreie Grammatik möglichst viele Dinge herausfinden zu können. Leider sind viele solche Probleme unentscheidbar. Als einfaches Beispiel:

Theorem 8.8.1 Wir wollen bestimmen, ob aus einer gegebenen kontextfreien Grammatik

G

ein Palindromwort ableitbar ist, also ein

γ

, das von rechts nach links gelesen gleich ist, sprich

γ = γ^{R}

. Dieses Problem ist unentscheidbar.

Formal gesehen müssten wir eine Codierung kontextfreier Grammatiken über einem festen Alphabet (zum Beispiel ${0, 1, \to,;, \dots}$ angeben, um dann die Sprache der Codierungen all jener kontextfreien Grammatik, die ein Palindromwort ableiten können definieren zu können. Da wir aber mittlerweile verstanden haben, dass alle "endlichen" Objekte irgendwie auf Turingmschinen-verträgliche Weise codiert werden können, ersparen wir uns diese Formalitäten.

Beweis. Wir zeigen: wenn man zu einer gegebenen kontextfreien Grammatik entscheiden könnte, ob sie ein Palindromwort ableiten kann, dann könnten wir auch entscheiden, ob ein gegebenes PCP-Puzzle eine Lösung hat. Da wir bereits Letzteres als unentscheidbar erkannt haben, schließen wir, dass Ersteres auch unentscheidbar ist.

Konkret sei uns nun also ein PCP-Puzzle $P$ gegeben. Wir bauen daraus eine kontextfreie Grammatik $G$ , so dass $G$ genau dann ein Palindromwort ableiten kann, wenn $P$ eine Lösung hat. Die Konstruktion ist überraschend einfach. Wir erschaffen ein Startsymbol $S$ für unsere Grammatik und erstellen zu jeder Kachel $α : β$ die Grammatikregel $\begin{aligned} S & \to α S β^{R}, \end{aligned}$ wobei $β^{R}$ das Wort $β$ von rechts nach links gelesen bedeutet, also $(x y z)^{R} = z y x$ . Wir fügen noch eine weitere Regel hinzu: $\begin{aligned} S & \to $, \end{aligned}$ wobei $$$ ein neues Zeichen ist, dass nicht in der Symbolmenge des PCP-Puzzles $P$ enthalten ist.

Behauptung 8.8.2 Wenn die Grammatik

G

ein Palindromwort ableiten kann, dann hat das PCP-Puzzle

P

eine Lösung.

Beweis. Die letzte angewandte Regel muss

S \to $

sein, und somit hat das abgeleitete Wort die Form

\begin{array}{r} α_{1} α_{2} \dots α_{n} $ β_{n}^{R} \dots β_{2}^{R} β_{1}^{R} . \end{array}

Jedes Paar

α_{i} : β_{i}

ist eine Kachel des PCP-Puzzles. Wenn das Wort ein Palindrom ist, dann gilt

α_{1} \dots α_{n} = β_{1} \dots β_{n}

und somit ist

\begin{array}{r} (α_{1} : β_{1}) (α_{2} : β_{2}) \dots (α_{n} : β_{n}) \end{array}

eine Lösung des PCP-Puzzles.

◻

Behauptung 8.8.3 Wenn das PCP-Puzzle

P

eine Lösung hat, dann kann die Grammatik

G

ein Palindromwort ableiten.

Beweis. Sei

\begin{array}{r} (α_{1} : β_{1}) (α_{2} : β_{2}) \dots (α_{n} : β_{n}) \end{array}

eine Lösung des Puzzles, also

α_{1} α_{2} \dots α_{n} = β_{1} β_{2} \dots β_{n}

. Dann ist auch

\begin{array}{r} α_{1} α_{2} \dots α_{n} $ (β_{1} β_{2} \dots β_{n})^{R} \end{array}

ein Palindrom und kann von

G

abgeleitet werden:

\begin{array}{r} S \Rightarrow α_{1} S β_{1}^{R} \Rightarrow α_{1} α_{2} S β_{2}^{R} β_{1}^{R} \Rightarrow \dots \Rightarrow α_{1} α_{2} \dots α_{n} S β_{n}^{R} \dots β_{2}^{R} β_{1}^{R} \Rightarrow α_{1} α_{2} \dots α_{n} $ β_{n}^{R} \dots β_{2}^{R} β_{1}^{R} \end{array}

Somit ist gezeigt, dass

G

ein Palindromwort ableiten kann.

◻

Hätten wir nun also einen Algorithmus, der für eine gegebene kontextfreie Grammatik entscheiden könnte, ob sie ein Palindromwort ableiten kann, dann könnten wir PCP-Puzzles wie folgt entscheiden: nimm das Puzzle

P

, baue nach den obigen Regeln daraus die Grammatik

G

und frage dann den Algorithmus, ob

G

ein Palindromwort ableiten kann. Dies beantwortet auch die Frage nach der Lösbarkeit des gegebenen PCP-Puzzles.

◻

Reduktionen

Es lohnt sich, an dieser Stelle zu pausieren. Was Sie gerade gesehen haben, ist eine Reduktion. Im "echten" Leben verwenden wir Reduktionen, um bereits gefundene Lösungen zu "recyceln". Beispielsweise:

Aufgabe: Zeigen Sie, dass die Funktion $n \mapsto n!$ im $λ$ -Kalkül berechenbar ist.
Wir wissen bereits, wie man $n \mapsto n!$ als primitiv-rekursive Funktion schreibt.
Wir wissen bereits, wie man eine allgemeine primitiv rekursive Funktion im $λ$ -Kalkül implementiert.
Wir schließen nun, dass $n \mapsto n!$ im $λ$ -Kalkül implementierbar ist, und ersparen uns die Details.

Im Kontext der Turing-Berechenbarkeit können wir dieses Prinzip wie folgt formalisieren:

Definition 8.8.4 Seien

L_{1} \subseteq Σ_{1}

und

L_{2} \subseteq Σ_{2}

zwei Sprachen. Eine Reduktion von $L_{1}$ nach $L_{2}$ ist eine Turing-berechenbare Funktion

\begin{array}{r} f : Σ_{1}^{*} \to Σ_{2}^{*} \end{array}

mit der Eigenschaft, dass

\begin{array}{r} \forall x \in Σ_{1}^{*} : x \in L_{1} \Leftrightarrow f (x) \in L_{2} . \end{array}

Erinnern Sie sich: dass $f$ Turing-berechenbar ist, heißt, dass es eine Turingmaschine $_{f}$ gibt mit einem dezidierten Ausgabe-Band, so dass $M_{f} (x)$ für jedes Eingabewort terminiert und zum Zeitpunkt der Terminierung $f (x)$ auf das Ausgabeband geschrieben hat. Wenn wir eine Reduktion von $L_{1}$ nach $L_{2}$ haben, dann liefert uns jeder Entscheidungsalgorithmus für $L_{2}$ unmittelbar einen Entscheidungsalgorithmus für $L_{1}$ :

Beobachtung 8.8.5 Wenn

f

eine Reduktion von

L_{1}

nach

L_{2}

ist und

L_{2}

entscheidbar ist, dann ist auch

L_{1}

entscheidbar.

Beweis. Sei

M_{2}

eine Turingmaschine, die

L_{2}

entscheidet und sei

M_{f}

die Turingmaschine, die

f

berechnet. Wir bauen nun eine neue Turingmaschine

M_{1}

. Sie nimmt das Eingabewort

x \in Σ_{1}^{*}

und lässt die Turingmaschine

M_{f}

auf

x

arbeiten; wenn

M_{f}

terminiert, steht

f (x)

auf ihrem Ausgabeband. Wir rufen nun die Turing-Maschien

M_{2}

mit dem Eingabewort

f (x)

auf. Wenn

M_{2}

akzeptiert (oder eben ablehnt), dann lassen wir

M_{1}

akzeptieren (oder eben ablehnen). Es gilt nun:

\begin{aligned} M_{1} (x) = accept & \Leftrightarrow M_{2} (f (x)) = accept \\ (weil M_{2} die Sprache L_{2} entscheidet) & \Leftrightarrow f (x) \in L_{2} \\ (weil f eine Reduktion ist) & \Leftrightarrow x \in L_{1} \end{aligned}

und somit entscheidet

M_{1}

die Sprache

L_{1}

◻

Stellen Sie sich einfach vor, dass

M_{f}

der Code ist, den Sie selber schreiben müssen, und

M_{2}

die "Bibliotheksfunktion" ist, die Sie ohne groß nachzudenken aufrufen, weil sie ja bereist von anderen Leuten (hoffentlich korrekt) implementiert worden ist. Behauptung 4.6.8 zeigt also, das etwas möglich ist. In der Berechenbarkeitstheorie und Komplexitätstheorie sind wir eher daran interessiert, zu zeigen, was nicht möglich ist, und wenden daher häufiger das Kontrapositiv der Behauptung an:

Beobachtung 8.8.6 Wenn

f

eine Reduktion von

L_{1}

nach

L_{2}

ist und

L_{1}

unentscheidbar ist, dann ist auch

L_{2}

unentscheidbar.

Beweis. Angenommen,

L_{2}

wäre entscheidbar. Dann wäre laut Behauptung 4.6.8 die Sprache

L_{1}

ja auch entscheidbar, was sie aber nach Annahme nicht ist. Daher ist

L_{2}

eben nicht entscheidbar.

◻

Beachten Sie nun, dass so etwas wie Behauptung 4.6.9 bereits oben angewandt haben: wir haben das Haltproblem auf das MPCP-Problem reduziert; jenes dann auf das PCP; und schließlich PCP auf das "Kann ein Palindrom abgeleitet werden"-Problem. Wir haben also eine ganze Kette von Reduktionen bereits durchgeführt. Für Neulinge ist diese Richtung oft inintuitiv und verwirrend. Dies spiegelt sich in der Verwendung des Konjunktivs wäre / wäre in Behauptung 4.6.9 wider. Auch ist es schlicht ungewohnt, ein altes Problem auf ein neues zu reduzieren statt umgekehrt.

Üben wir also Reduktionen:

Theorem 8.8.7

(Schnittproblem kontextfreier Sprachen)

Gegeben zwei kontextfreie Grammatiken

G_{1}, G_{2}

. Es ist unentscheidbar, ob

L (G_{1}) \cap L (G_{2})

nichtleer ist, ob es also ein Wort

x

mit

x \in G_{1}

und

x \in G_{2}

gibt.

Dieses Problem ist als Schnittproblem kontextfreier Sprachen bekannt.

Beweis. Wir reduzieren das Palindromwortproblem (bereits bekannt) auf das Schnittproblem (neues Problem). Sei

G

eine Grammatik und

Σ

die Menge der Terminalsymbole. Sei

G^{'}

die folgende Grammatik:

\begin{aligned} (für alle x \in Σ) & S^{'} & \to x S^{'} x \\ (für alle x \in Σ) & S^{'} & \to x \\ S^{'} & \to ϵ \end{aligned}

Die Grammatik

G^{'}

erzeugt genau die Sprache der Palindromwörter über

Σ

. Unsere Reduktion

f

nimmt nun als Eingabe eine kontextfreie Grammatik

G

(bzw. deren Codierung) und gibt das Paar

(G, G^{'})

aus (bzw. deren Codierungen). Wir stellen fest:

G

kann ein Palindromwort ableiten genau dann, wenn

L (G) \cap L (G^{'}) \neq \emptyset

, wenn es also ein Wort

α

gibt, dass aus

G

und aus

G^{'}

abgeleitet werden kann. Die Funktion

f

ist also eine Reduktion vom Palindromwortproblem auf das Schnittproblem. Mit Behauptung 4.6.9 zusammen heißt das, dass das Schnittproblem unentscheidbar ist.

◻

Theorem 8.8.8 (Mehrdeutigkeitsproblem kontextfreier Sprachen) Gegeben eine kontextfreie Grammatik

G

. Es ist unentscheidbar, ob

G

mehrdeutig ist, d.h., ob es ein Wort

x \in Σ^{*}

gibt, für das zwei verschiedene Ableitungsbäume existieren.

Falscher Beweis. Wir reduzieren das uns bereits bekannte Schnittproblem auf das Mehrdeutigkeitsproblem. Gegeben seien zwei kontextfreie Grammatiken

G_{1}, G_{2}

mit Startsymbolen

S_{1}, S_{2}

und Nichtterminalmenge

N_{1}, N_{2}

. Wir machen in einem ersten Schritt die Mengen

N_{1}

und

N_{2}

disjunkt (wenn sie es nicht eh schon sind; wir können beispielsweise jedes

X \in N_{2}

X^{'}

umbenennen). Dann führen wir ein Super-Startsymbol

S

ein und zwei Produktionen:

\begin{aligned} S & \to S_{1} \\ S & \to S_{2} \end{aligned}

und übernehmen alle Produktionen von

G_{1}

und

G_{2}

. Dies ist unsere neue Grammatik

G

. Sie sehen nun: wenn es ein

x \in L (G_{1}) \cap L (G_{2})

gibt, dann kann man

x

auf zwei verschiedene Weisen in

G

ableiten, nämlich

\begin{aligned} (Ableitung wie in G_{1}) & S & \Rightarrow S_{1} \Rightarrow^{*} x \\ (Ableitung wie in G_{2}) & S & \Rightarrow S_{2} \Rightarrow^{*} x, \end{aligned}

und das sind wirklich zwei verschiedene Ableitungen, weil ja bereits

S_{1} \neq S_{2}

. Wenn nun umgekehrt ein Wort

y

via

S_{1}

und via

S_{2}

ableitbar sein sollte (

G

also mehrdeutig sein sollte), dann bedeutet dies, dass

G_{1}

und

G_{2}

beide das Wort

y

ableiten können, also einen nichtleeren Schnitt haben. Dies ist somit unsere Reduktion

f

: nimm als Eingabe das Paar

G_{1}, G_{2}

(bzw. dessen Codierung), konstruiere

G

und gib

G

aus. Dieses

f

reduziert das Schnittproblem auf das Mehrdeutigkeitsproblem.

◻

Haben Sie den Fehler im Beweis erkannt? Das Problem ist, dass es sein könnte, dass $G_{1}$ und $G_{2}$ leeren Schnitt haben, $G_{1}$ aber bereits mehrdeutig ist. Die Ausgabe-Grammatik $G$ wäre dann auch mehrdeutig; also hätte die Reduktion $f$ einen Fehler gemacht. Wir müssen leider bis zum Postschen Korrespondenzproblem zurückgehen und direkt von dort reduzieren. Problematisch ist, dass ein PCP-Puzzle selbst mehrere Lösungen haben kann und auch für ein Lösungswort $γ$ es mehrere Möglichkeiten geben kann, es zu "legen", also $\begin{aligned} top (s) & = bottom (s) = γ \\ top (s^{'}) & = bottom (s^{'}) = γ . \end{aligned}$ Wenn dem so wäre, dann würde bereits unsere Reduktion auf das Palindromwortproblem eine mehrdeutige Grammatik erzeugen. Wir gehen einen anderen Weg. Ich folge hier dem Tip in Exercise 5.21 aus Michael Sipsers Buch Introduction to the Theory of Computation, third edition.

Beweis. Sei ein PCP-Puzzle

P = {(α_{1} : β_{1}), \dots, (α_{n} : β_{n})}

gegeben. Wir erstellen nun eine kontextfreie Gramatik, die es dem "User" erlaubt, zu entscheiden, ob er das Wort via die oberen Teile

α_{i}

oder via die unteren Teile ableiten will; wenn es auf beide Weisen geht, dann ist die Grammatik mehrdeutig und das PCP hat eine Lösung. Also:

\begin{aligned} S & \to S_{1} \\ S & \to S_{2} \\ (für alle oberen Teile α_{i}) & S_{1} & \to α_{i} S_{1} i | α_{i} i \\ (für alle unteren Teile β_{i}) & S_{2} & \to β_{i} S_{2} i | β_{i} i \end{aligned}

wobei

1, 2, \dots, n

neue Symbole sind. Die Indizes

i

stellen sicher, dass jede von

S_{1}

ausgehende Ableitung eindeutig ist (und genau so von

S_{2}

); die einzige Mehrdeutigkeit kann aufkommen, wenn ein Wort sowohl via

S_{1}

als auch via

S_{2}

ableitbar ist; und dies geschieht genau dann, wenn das PCP-Puzzle eine Lösung hat. Wir haben nun also unsere Reduktion von PCP auf das Mehrdeutigkeitsproblem.

◻