Rekursive Sprache

Definition und Abgrenzung

In der theoretischen Informatik heißt eine formale Sprache L über einem Alphabet Σ rekursiv oder entscheidbar, wenn es eine Turingmaschine M gibt, die auf allen Eingaben w ∈ Σ* hält und eine Eingabe w genau dann akzeptiert, wenn w ∈ L ist. Σ* bezeichnet dabei die Menge aller Wörter über dem Alphabet Σ.

Der entscheidende Punkt ist das Halten auf allen Eingaben: Für eine rekursive Sprache muss die Turingmaschine für jedes mögliche Wort zu einer Ja- oder Nein-Antwort kommen. Das unterscheidet rekursive Sprachen von rekursiv aufzählbaren Sprachen. Bei einer rekursiv aufzählbaren Sprache muss die Turingmaschine nur dann halten, wenn das eingegebene Wort tatsächlich zur Sprache gehört; für Wörter außerhalb der Sprache darf sie endlos weiterlaufen.

Berechenbarkeit und Entscheidungsprobleme

Die Menge der rekursiven Sprachen stimmt mit allen bisher vorgeschlagenen Berechenbarkeitsmodellen überein. Dazu gehören besonders die Goto-Berechenbarkeit und die While-Berechenbarkeit, die aus gängigen Programmierkonstrukten am Computer hervorgehen. Diese Übereinstimmung ist ein Ausgangspunkt für die Churchsche These.

Nach der Churchschen These gibt es für ein Entscheidungsproblem überhaupt keinen Algorithmus, wenn es keine Turingmaschine gibt, die dieses Problem löst. Ein Entscheidungsproblem ist ein Problem, dessen Antwort nur Ja oder Nein sein kann. Obwohl diese Einschränkung zunächst stark wirkt, ist sie meist ausreichend, weil die zugehörigen Berechnungsprobleme meist nicht schwieriger zu lösen sind.

Wichtig ist außerdem: Die durch primitive Rekursion erzeugten Sprachen bilden nur eine echte Teilmenge der rekursiven Sprachen. Man kann zeigen, dass dies genau die Sprachen sind, die auch durch Loop-Berechenbarkeit erzeugt werden.

Einordnung in die Chomsky-Hierarchie

Die rekursiven Sprachen liegen in der Chomsky-Hierarchie zwischen zwei wichtigen Sprachklassen. Sie sind eine echte Teilmenge der Chomsky-Typ-0-Sprachen, also der rekursiv aufzählbaren Sprachen. Zugleich sind sie eine echte Obermenge der Chomsky-Typ-1-Sprachen, also der kontextsensitiven Sprachen.

Daraus folgen zwei wichtige Aussagen: Das Halteproblem ist rekursiv aufzählbar, also Typ 0, aber nicht rekursiv. Außerdem gibt es Sprachen, die rekursiv, aber nicht kontextsensitiv, also nicht Typ 1, sind.

Sprachen, Grammatiken und Automaten

Der Vorteil der Definition über Sprachen ist, dass sich alle Entscheidungsprobleme auf Sprachen zurückführen lassen. Für ein Entscheidungsproblem P gilt: Eine Eingabe w ist genau dann eine Lösung, wenn w in der zu P gehörenden Sprache L liegt. Das nennt man das Wortproblem.

Dadurch entsteht eine Brücke zwischen zwei Sichtweisen: dem erzeugenden Grammatik-Modell und dem akzeptierenden Automaten-Modell. Sprachen können unter anderem durch Chomsky-Grammatiken beschrieben werden, während Automaten wie Turingmaschinen Sprachen akzeptieren. Zu jeder Chomsky-Grammatik-Klasse gibt es eine Automatenklasse, die genau die Sprachen dieser Klasse akzeptiert, und umgekehrt. Das ist der Zusammenhang der Chomsky-Hierarchie.

Die Nicht-Rekursivität einer Sprache kann man mit dem Satz von Rice nachweisen.