Kommentare zur Reduktion

Diese Reduktion ist weder neu, noch überraschend. Ich will stattdessen diese Benutzen um langsam aber sicher den Reduktionsprozess zu analysieren.

Zunächst die Definitionen:

\[ \mathrm{H} := \left\{ \left\langle M \right\rangle w \;|\; M \text{ist det. 1-Band-TM, die mit } w \text{ gestartet, hällt } \right\} \] und \[ \mathrm{H}_{\varepsilon} := \left\{ \left\langle M \right\rangle \;|\; M \text{ ist det. 1-Band TM die mit leerem Band, hällt}\right\} \]

Eine Sitze des Beweises, dass \(\mathrm{H} \leq \mathrm{H}_{\varepsilon}\) gilt, dh. für jedes Wort \(w\) das in \(\mathrm{H}\) sein könnte, oder nicht, kann ein anderes Wort \(\tilde{w}\) berechnet werden, welches genau dann in \(\mathrm{H}_{\varepsilon}\) enthalten sein wird, wenn auch \(w\) in \(\mathrm{H}\) enthalten ist. Da dieses als Lösung für das Unlösbare Wortproblem des Halteproblems benutzt werden kann, ist zu folgern das \(\mathrm{H}_{\varepsilon}\) ebenfalls nicht entscheidbar ist.

Der gesamte Bewies teilt sich in zwei Teile:

1. Konstruktion der Reduktionsfunktion
2. Nachweis der Korrektheit der Funktion

Die Funktion muss, wie bereits erwähnt, von ganz \(\left\{ 0, 1 \right\}\) auf \(\left\{ 0, 1 \right\}\) abbilden müssen, da Reduktionen vollkommen und berechenbar sein müssen.

Dieses bedeutet das alle syntaktisch-invaliden Eingaben, dh. Wörter die nicht als Turingmaschine und Eingabe interpretiert werden können, und als solche auch nicht als Bestandteile von \(\mathrm{H}\) angesehen werden können, auch nicht Bestandteile von \(\mathrm{H}_{\varepsilon}\) sein dürfen. Die einfachste Möglichkeit dieses zu erreichen, ist im Falle einer misslungenen Syntaxanalyse, einfach 0 zurückzugeben, für Gödelnummer-Verschlüsselungen die 0 nicht produzieren können. Gelegentlich habe ich auch das zurückgeben der Eingabe gesehen, was dann funktionieren sollte, wenn der Erfolg der Analyse ausschließlich von der Korrektheit.

Die Reduktion muss daher Minimal die Form \[ f(x) = \begin{cases} \ldots & \text{wenn } x = \left\langle M \right\rangle w \\ 0 & \text{sonst} \end{cases} \] annehmen, für ein \(w\) nach Problemstellung.

Es kann also nun angenommen werden, das alle noch zu behandelnden Fälle Syntaktisch Korrekt sind, im Fall der \(\mathrm{H} \leq \mathrm{H}_{\varepsilon}\) Reduktion Gödelnummern von Turing Maschinen \(M\), gefolgt von deren Eingaben \(w\). Abhängig von eben diesen ermittelten Objekten, soll eine neue Maschine konstruiert werden. In diesem Fall wird von der Gefordert, dass diese Haltet wenn \(M\) gestarted mit \(w\) haltet und die Eingabe der Maschine selbst das Leere Wort \(\varepsilon\) ist.

Die Beschreibung der notwendigen Lösung ermöglicht die Konstruktion einer parametrisierten Turingmachine, die eben dieses macht:

\(FesteMaschine_{\left\langle M \right\rangle w}\):

1. Lese Eingabe und vermerke diese als \(x\)
2. Simuliere parametrisiertes \(M\) mit der parametrisierten Eingabe \(w\)
3. Falls \(x = \varepsilon\), halte
4. Starte eine Endlosschleife

Unter Zurhernahme der Gödelnummer \(\left\langle FesteMaschine_{\left\langle M \right\rangle w} \right\rangle\) kann die obige Reduktionsfunktion vervollständigt werden: \[ f(x) = \begin{cases} \left\langle FesteMaschine_{\left\langle M \right\rangle w} \right\rangle & \text{wenn } x = \left\langle M \right\rangle w \\ 0 & \text{sonst} \end{cases} \]

Mit einer konstruierten Funktion, kann betrachtet werden, ob diese Tatsächlich das zu Erwartende berechnet. Der Fall für die Syntaktische Inkorrektheit wurde bereits oben erwähnt, und wird somit im Folgendem übersprungen.

Die Fragestellung lautet \[ w \in L_u \stackrel{?}{\Leftrightarrow} f(w) \in L_r, \] wo \(L_u = \mathrm{H}\) und \(L_r = \mathrm{H}_{\varepsilon}\). Um dieses zu beantworten, muss die eine Fallunterscheidung betrachtet werden (nochmal, für nur syntaktisch korrekte Eingaben \(w\)):

Für den Fall \(w \in \mathrm{H}\)

Da die durch \(w\) dargestellte TM \(M\) mit Eingabe \(w^{\prime}\) haltet, wird erwartet das \(f(w)\) auch haltet.

\(f\) wird wie leicht einzusehen ist \(\left\langle FesteMaschine_{\left\langle M \right\rangle w} \right\rangle\) zurückgeben, welches wir mit den konkreten Parametern \(M\) und \(w^{\prime}\) betrachten, nach oben aufzählten Schritten:

1. Lesen der Eingabe erfolgt unkontrovers, da dieses eine geläufige Fähigkeit von TMs ist.

2. Da wir wissen das \(M\) in \(\mathrm{H}\) ist (durch obige Annahme, nicht durch eine Berechnung), wissen wir das dieser Schritt terminieren muss, da wenn \(M\) haltet, dessen Simulation auch (in endlicher Zeit) haltet.

   Schritt 3 wird also erreicht.

3. Es wird geschaut ob die in Schritt 1 eingelesene Eingabe \(x\) das leere Wort ist, und nur dann gehalten.

4. Wir erreichen diesen Schritt wenn \(w \in \mathrm{H}\), aber \(x \neq \varepsilon\). Obwohl dieses auf dem erstem Blick kontraintuitiv scheinen mag, ist dieses vollkommen valide.

   Es wird verlangt, dass wenn \(w \in \mathrm{H}\), dass die neue Maschine dann haltet, wenn die Eingabe leer ist. Ist sie dieses nicht, haltet diese nicht, was durch eine Endlosschleife bewirkt wird.

Für den Fall \(w \notin \mathrm{H}\)

Alle Umstände sind analog zum vorherigem Fall. Die Feste Maschine wird wieder de-parametrisiert gestartet, und die Schritte betrachte:

1. Analog zum obigem erstem Fall
2. Dadurch das \(w \in \mathrm{H}\) gilt, muss gefolgert werden das die Simulation nicht halten, nicht terminieren und somit der gesamte Algorithmus nicht fortschreiten kann. Es wird keine Berechnung weitere Berechnung getätigt, und keine Möglichkeit zugelassen einen Wert zurückugeben.
3. Schritt 3 kann nicht erreicht werden

4. Schritt 4 kann nicht erreicht werden

   Wir sehen also, das da \(w \in \mathrm{H}\), die durch \(f(w)\) beschriebene Funktion weder für Eingaben gleich oder ungleich \(\varepsilon\) haltet, wie verlangt.

Somit wurde eine Funktion beschrieben, und dessen Korrektheit hinsichtlich der Reduktionsvorraussetzung nachgewiesen.

Die Sprache \[ \text{Anf\_Ungleich\_End} = \left\{ \, \mathrm{bin}(a_1) \; \# \; \ldots \; \# \; \mathrm{bin}(a_n) \;|\; n \geq 2, a_1 \neq a_n \right \} \] ist in nach einem "Braindump" der BFS Klausur, des Wintersemesters 16/17 vorgestellt worden. Es galt zu zeigen: \(\text{Anf\_Ungleich\_End} \leq_p \mathrm{SAT}\).

Dieses heißt zunächst: Für jedes Wort aus \(\text{Anf\_Ungleich\_End}\) muss eine Formel gefunden werden, die erfüllbar ist, und analog darf jede Formel die nicht aus der Sprache ist nicht erfüllbar sein: \[ w \in \text{Anf\_Ungleich\_End} \Leftrightarrow f(w) \in \mathrm{SAT} \]

Im folgendem sei \(\text{Anf\_Ungleich\_End}\) mit \(L\) abgekürzt.

Die notwendigen, inhaltlicht-unabhängigen, Bedingungen von \(f\) sind also:

• Totalität
• Berechenbarkeit allgemein
• Berechenbarkeit mit \(\mathcal{O}(n^k)\) Schritten in Abhängigkeit von der Eingabe.

Die angegebene Sprache \(L\) fordert nur das von den mehr als zwei (\(n \geq 2\)) Binärzahlen die in dem Wort kodiert sind (\(\mathrm{bin}(a_1) \; \# \; \ldots \; \# \; \mathrm{bin}(a_n)\)), die erste und die letzte Ungleich sind (\(a_1 \neq a_n\)). Ist dieses der Fall, soll eine erfüllbare Formel produziert werden (bspw. \(A \land B\), \(A \lor \neg A\), oder \(A\)), ansonsten eine nicht erfüllbare (bspw. \(A \land \neg A\), oder eine leere Klauselmenge).

Ohne dass man genau weiß wie dieses analytisch/berechenbar beschrieben werden soll, kann man die Folgende Form einer Reduktionsfunktion angeben \[ f(x) = \begin{cases} \left\langle A \land B \right\rangle & \text{\textit{Im positivem Fall}}\\ \left\langle A \land \neg A \right\rangle & \text{sonst}\\ \end{cases} \]

(Anstatt \(\left\langle A \land \neg A \right\rangle\) könnte man auch 0 generieren – da dieses ebenso wenig in \(\mathrm{SAT}\) ist wie die Formel.)

Es ist zu erinnern, dass \(x\) ein Wort über bspw. \(\left\{ 0, 1, \# \right\}\) ist, und daher eine Syntaxanalyse notwendig sein wird. Da gültige Wörter eine Folge von binären Zahlen und und \(\#\) Zeichen sind, kann dieses in polynomischer, wenn nicht linearer Zeit gelesen werden (bspw. durch eine einfache Kontextfrei-Grammatik und eines beliebigen Polynomzeit- oder schneller Parser: LR(k), LL, CYK, Earley, …).

Auf einer höheren Abstraktionsebene kann man sich also vorstellen das alle Zahlen (oder Zeichenketten – da keine Arithmetik betrieben wird ist es der Unterschied zu vernachlässigen) in einer Liste gespeichert werden. Nun muss geschaut werden:

1. Ist die Länge der Liste größer als 2?
2. Ist das erste und letzte Element der Liste ungleich?

Die erste Operation braucht \(\mathcal{O}(1)\) Schritte, die zweite (abhängig von der Umsetzung im Berechenbarkeits-Modell) sollte nicht schlimmer als \(\mathcal{O}(n) + \mathcal{O}(1) = \mathcal{O}(n)\) sein. Beide sind neben der Syntaxanalyse vernachlässigbar.

Unter der Gewissheit dass die Methode in Polynomialzeit berechenbar ist, kann die obige Reduktionsfunktion vervollständigt werden: \[ f(x) = \begin{cases} \left\langle A \land B \right\rangle & x = a_1 \; \# \; \ldots \; \# \; a_n, a_1 \neq a_n \\ \left\langle A \land \neg A \right\rangle & \text{sonst}\\ \end{cases} \]

Wir sehen also \[ x \in L \Rightarrow f(x) = \left\langle A \land B \right\rangle \in \mathrm{SAT}, \] da \(A \land B\) mit \(A \leftarrow \top\) erfüllt werden kann, gilt, wie auch \[ x \notin L \Rightarrow f(x) = \left\langle A \land \neg A \right\rangle \notin \mathrm{SAT}, \] nach hier irrelevanten Gesetzen der Logik.

Es wurde also gezeigt, dass \(\text{Anf\_Ungleich\_End} \leq_p \mathrm{SAT}\) gilt, also das jedes Wort aus \(\text{Anf\_Ungleich\_End}\) auf eine Formel abgebildet werden kann.

Beachtet das dieses nicht bedeutet das \(\text{Anf\_Ungleich\_End}\) in \(\mathrm{NP}\) ist. Die Tatsache das einfache Probleme, komplex formuliert werden können ist ein gesellschaftliches, nicht mathematisches. Das obige Problem kann auch ohne Reduktion (wie auch alle anderen Probleme in \(NP\)) gelöst werden:

bool Anf_Ungleich_End(char *w) {
     char *first = strtok(w, '#');
     char *last, *next;
     while (next = strtok(NULL, '#'))
          last = next;
     return !!strcmp(first, last);
}

sollte in \(\mathcal{O}(n)\), ohne Umweg über \(\mathrm{SAT}\) auf die gleiche Lösung kommen.