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]++

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: True
   Fa: False

Dieser Algorithmus terminiert garantiert.

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