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