Entscheidbarkeit

Wir wollen nun Sprachen klassifizieren. Die Frage, ob ein Wort in einer Sprache vorkommt, nennt sich das Entscheidungsproblem dieser Sprache. In der Literatur bezeichnet man mit dem Entscheidungsproblem allerdings teilweise auch nur ein ganz spezielles Problem, nämlich das Entscheidungsproblem der Menge der wahren mathematischen Aussagen.

Zu diesem Zweck müssen wir jedenfalls irgendwie vereinbaren, dass die Rechenmaschine uns "Wahr" und "Falsch" zurückliefern kann. Wir können dazu bei Turingmaschinen zusätzliche Spezialzustände einführen, und für Registermaschinen Befehle return true und return false. Wie genau wir es machen ist aber letztendlich egal, die meisten Methoden sind offensichtlich äquivalent.

Entscheidbare Sprachen

Eine Sprache $\frak L$ heißt entscheidbar, wenn es einen Algorithmus gibt, der für alle Wörter terminiert, und genau dann "Wahr" zurückliefert, wenn das übergebene Wort in $\frak L$ liegt. Es sind also die Sprachen, für die es einen effektiven Algorithmus gibt. Beispielsweise ist ${\cal L}^*$ immer entscheidbar, genauso $\emptyset$. Die Menge der geraden Zahlen, genauso wie die Menge der Primzahlen.

Einen effektiven Algorithmus zu haben heißt aber nicht, dass dieser auch effizient sein muss. Die zugehörige Maschine muss irgendwann terminieren. Wie lange sie ansonsten brauchen darf, ist nicht begrenzt.

Lemma: Ist $\frak L$ entscheidbar, so ist auch $\overline{\frak L}$ entscheidbar.

Beweis: Übung.

TODO

Aufzählbare Sprachen

Wir erweitern Registermaschinen um einen Befehl print R[i]. Die Intuition ist, dass solche Registermaschinen eine Folge von Werten ausgeben, und zwar einen Wert mit jedem print-Befehl.

Eine Sprache $\frak L$ heißt nun aufzählbar, wenn es eine Registermaschine gibt, die jedes Element irgendwann print-ed.

Lemma: Jede entscheidbare Menge ist aufzählbar.

Beweis: Sei $\frak L\subseteq\mathbb{N}$ entscheidbar, und werde durch das Programm $E$ entschieden. Dann zählt das folgende Programm die Menge auf:

   Start: if E(R[1]) then goto Pr
   R[1]++
   goto Start
   
   Pr: print R[1]
   R[1]++
   goto Start

Lemma: Die Menge der Lösungen eines gegebenen diophantischen Gleichungssystems $D(x_1,\ldots,x_n)=0$ ist aufzählbar.

Beweis: Die Idee ist, einfach alle $n$-tupel $(x_1,\ldots,x_n)$ durchzuprobieren, und die, für die es passt, auszugeben.

Satz: Die Menge der terminierenden Turingmaschinen $\frak T$ ist aufzählbar.

Beweis: Bezeichne $T_i$ die durch $i\in\mathbb{N}$ codierte Turingmaschine. Offensichtlich ist entscheidbar, ob $T_i$ nach $k$ schritten terminiert: Man muss $T_i$ nur $k$ schritte simulieren, und schauen, ob sie in dieser Zeit terminiert. Sei $T_i^k = \top$, falls $T_i$ nach höchstens $k$ schritten terminiert, und $T_i^k = \bot$ sonst. Dann zählt folgender Algorithmus alle terminierenden Turingmaschinen auf:

   Start: if T[R[0],R[1]] == ‾|‾ then print R[0]
   R[0]++
   if R[0] > R[1] then goto Rst
   goto Start
   
   Rst: R[0] := 0
   R[1]++
   goto Start

Der Algorithmus probiert alle $T_i^k$ durch, in der Reihenfolge $T_0^0, T_0^1, T_1^1, \ldots$.

Semi-Entscheidbare Sprachen

Eine Sprache $\frak L$ heißt Semi-Entscheidbar, wenn es einen Algorithmus $M(n)$ gibt, der als Eingabe eine natürliche Zahl $n$ erhält, und ein Wort oder $\bot$ ausgibt, sodass es genau für die Wörter in $\frak L$ eine Eingabe $n$ gibt. Formaler ist also $M:\mathbb{N}\rightarrow \{\bot\}\cup{\frak L}$ surjektiv.

Lemma: Semi-Entscheidbare Sprachen sind Aufzählbar

Beweis: Sei ${\frak L}\subseteq\mathbb{N}$ semi-entscheidbar mit zugehörigem $M:\mathbb{N}\rightarrow \{\bot\}\cup{\frak L}$. Dann wird $\frak L$ von folgendem Programm aufgezählt:

   Start: if M(R[0]) == _|_ then goto Cont
   print M(R[0])
   Cont: R[0]++
   goto Start
   

Lemma: Aufzählbare Sprachen sind Semi-Entscheidbar

Beweis: Sei ${\frak L}\subseteq\mathbb{N}$ aufzählbar und werde von $M$ aufgezählt. Sei $M_i = \bot$, falls $M$ nach $i$ Schritten eine andere Anweisung als print ausführt, ansonsten, falls die Anweisung nach $i$ Schritten print R[j] ist, $M_i=R_j$. Offenbar ist $M_i$ für jedes $i$ berechenbar, denn man muss ja nur die Registermaschine $M$ für $i$ schritte simulieren. Die zurückgelieferte Funktion $i\mapsto M_i$ ist offenbar von der Form, dass sie $\frak L$ semi-entscheidet.

Damit sind Semi-Entscheidbarkeit und Aufzählbarkeit also äquivalent, und damit zwei Arten, über die selbe Sache nachzudenken.

Lemma: Eine Sprache $\frak L$ ist genau dann entscheidbar, wenn sowohl $\frak L$ als auch $\overline{\frak L}$ semi-entscheidbar sind.

Beweis: "$\Rightarrow$" ist trivial. "$\Leftarrow$": Seien $M : \mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ und $\overline{M}:\mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ entsprechend gegeben. Dann entscheidet folgendes Programm $\frak L$:

   Start: if M(R[1]) == R[0] then goto Tr
   if ‾M(R[1]) == R[0] then goto Fa
   R[1]++
   goto Start
   
   Tr: return True
   Fa: return False

Dieser Algorithmus terminiert garantiert.

Korollar: Die Menge der nicht terminierenden Turingmaschinen ist nicht semi-entscheidbar.

Beispiel: Das Post'sche Korrespondenzproblem

Gegeben eine Menge an Dominosteinen bei denen jeweils oben und unten eine Zeichenkette steht, gibt es eine Folge an Dominos, so dass die Konkatenation der Ketten oben und unten gleich sind? (Dabei dürfen Steine mehrmals verwendet werden.)

Beispiel:

    (1)  (2)   (3)
   [ 1 ] [10] [011]
   ----- ---- -----
   [101] [00] [ 11]

Überlegung: Damit die ersten beiden Zeichen des konkatenierten Strings gleich sein können, muss der erste Stein (1) sein. Dann muss das erste Zeichen des oberen Strings eine 0 sein, also ist der nächste Stein (3). Als nächstes könnte man sowohl (1) oder (2) nehmen, damit der untere String im Vergleich zum oberen aber nicht immer länger nimmt nehmen wir (2). Als nächsten Stein müssen wir wieder (3) nehmen und damit haben wir auch eine Lösung gefunden.

Lösung:(1)(3)(2)(3)

Offensichtlich können wir Lösungen miteinander konkatenieren um neue (beliebig lange) Lösungen zu erhalten. Wenn kein Teil einer Lösung für sich stehend eine Lösung ist nennen wir sie primitiv.

Keine Lösung gibt es zB für:

   [11] [01]
   ---- ----
   [ 1] [ 0]

(Der obere String ist immer länger als der untere)

Eine Formalisierung dieses Problems ist folgendermaßen:

Gegeben eine Menge $K$ von Paaren $(x_i,y_i)$ aus nichtleeren Wörtern über einem Alphabet $\Sigma$. Es soll entschieden werden ob eine korrespondierende Folge von Indizes $i_1,...,i_n \in {1,...,k}, n \geq 1$ gibt, so dass $x_(i_1),...,x_(i_n) = y_(i_1),...,y_(i_n)$.

Wir wollen zeigen, dass dieses Problem nicht entscheidbar ist.

Dazu werden wir zeigen, dass sich das Halteproblem auf eine modifizierte Version des PKPs reduzieren lässt, die sich wiederum auf das PKP reduzieren lässt. Wenn es also einen allgemeinen Algorithmus zur Entscheidung des PKPs gäbe, müsste es auch einen allgemeinen Algorithmus für das Halteproblem geben.

mPKP:

Gegeben eine Menge $K$ von Paaren $(x_i,y_i)$ aus nichtleeren Wörtern über einem Alphabet $\Sigma$. Es soll entschieden werden ob eine korrespondierende Folge von Indizes $i_2,...,i_n \in {1,...,k}, n \geq 1$ gibt, so dass $x_1,...,x_(i_n) = y_1,...,y_(i_n)$.

Wir zeigen die Äquivalenz der beiden Probleme in dem wir eine Funktion $f$ basteln die ein Set $K$ von Dominos in ein neues Set $f(K)$ überführt, so dass eine Lösung für mPKP über K auch eine Lösung für PKP ist und umgekehrt.

Sei $K = \{[\frac{x_1}{y_1}],...,[\frac{x_1}{x_k}]\}$, dann sei $f(K) = \{[\frac{x'_0}{y'_0}],[\frac{x'_1}{y'_1}],...,[\frac{x'_k}{y'_k}],[\frac{x'_{k+1}}{y'_{k+1}}]\}$ mit

• $x'_i$ aus $x_i$ entsteht, indem wir hinter jedes Zeichen ein # einfügen
• $y'_i$ aus $y_i$ entsteht, indem wir vor jedes Zeichen ein # einfügen

Außerdem gelte $x'_0 = \# x'_1$, $ x'_{k+1} = \$ $, $y'_0 = y'_1$ und $y'_{k+1} = \#\$ $

Beispiel: $ K= \{ [\frac{ab}{a}],[\frac{c}{abc}],[\frac{c}{abc}]\}$ wird zu $ f(K) = \{[\frac{\#a\#b\#}{\#a}],[\frac{a\#b\#}{\#a}],[\frac{c\#}{\#a\#b\#c}],[\frac{a\#}{\#b}],[\frac{\$}{\#\$}]\}$

mPKP -> PKP

Sei $(1,i_2,...i_n)$ eine Lösung für $K$, d.h. $x_1 x_{i_2} x_{i_n} = y_1 y_{i_2}... y_{i_n} = a_1 a_2 ... a_1$ so dass $a_1...a_s$ Symbole aus $\Sigma$.

Dann ist $(0, i_2,....,in,k+1)$ eine Lösung für $f(K)$, denn $$x'_0x'_{i_2}...x'_{i_n}\$ = \#a_1\#a_2...\#a_s\#\$ = y'_0y'_{i_2}...y'_{i_n}\#\$ $$

Wenn es also eine Lösung für $K$ bzgl. mPKP, so gibt es auch eine Lösung für $f)K=$ bgzl. PKP.

PKP -> mPKP

Sei nun(i_1,i_2,...,i_n) eine primitve Lösung für $f(K)$:

• Es gilt $i_1=0$ und $i_n = k+1$, weil nur $x'_0$ und $y'_0$ mit demselben Zeichen beginnen und nur $x'_{k+1}$ und $y'_{k+1} mit demselben Zeichen enden.
• Es gilt $i_j$ \neq 0$ für $2\leq j \leq n$, weil sonst zwei # oben aufeinanderfolgen, was unten nicht sein kann.
• Es gilt $i_j \neq k+1$ für $1\leq j < n$, weil sonst die Folge bis $i_j$ auch eine Lösung wäre (Widerspruch zur geforderten Primitivität der Lösung)

Also sieht unsere Lösung für PKP folgendermaßen aus: $$x'_0x'_{i_2}...x'_{i_n} = \#a_1\#a_2...\#a_s\#\$ = y'_0y'_{i_2}...y'_{i_n} $$ woraus wir die mPKP Lösung $$x_1 x_{i_2} x_{i_n} = y_1 y_{i_2}... y_{i_n} = a_1 a_2 ... a_1$$

Wenn man mPKP lösen kann, kann man also auch PKP lösen.

(Fortsetzung: [1]