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.

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.

TODO

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.