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