Rekursiv aufzählbare Sprache
aus Wikipedia, der freien Enzyklopädie
Eine rekursiv aufzählbare Sprache oder semientscheidbare Sprache L ist dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus L akzeptiert, aber keine Wörter, die nicht in L liegen. Im Unterschied zu rekursiven Sprachen oder entscheidbaren Sprachen muss bei den rekursiv aufzählbaren Sprachen die Turingmaschine nicht halten, wenn ein Wort nicht in L liegt. Das heißt, unter Umständen muss man auf die Lösung „unendlich lange“ warten. Alle rekursiven Sprachen sind deshalb auch rekursiv aufzählbar.
Rekursiv aufzählbare Sprachen bilden die unterste Stufe der Chomsky-Hierarchie und heißen deshalb auch Typ-0-Sprachen (oder Grammatiken). Sie können somit auch als all die Sprachen definiert werden, deren Wörter sich durch eine beliebige formale Grammatik ableiten lassen.
Eines der wichtigsten Probleme, das rekursiv aufzählbar ist, aber nicht rekursiv, ist das so genannte Halteproblem.
Ein nicht semi-entscheidbares Problem ist die so genannte Diagonalsprache: die Menge der Codierungen all derer Turingmaschinen, die auf ihrer eigenen Codierung als Eingabe nicht halten.
D = {<M> | M hält nicht auf <M>}
Auch das Komplement des (semi-entscheidbaren) Halteproblems ist nicht semi-entscheidbar, während das Komplement der Diagonalsprache semi-entscheidbar ist (in der Tat ist das Komplement des Halteproblems ein Spezialfall der Diagonalsprache und das Komplement der Diagonalsprache eine Erweiterung des Halteproblems).
Allgemein gilt für eine Sprache L und ihr Komplement K(L) stets genau eine der folgenden drei Eigenschaften:
- L und K(L) sind rekursiv (und somit auch rekursiv aufzählbar).
- L und K(L) sind nicht rekursiv aufzählbar.
- Genau eine der Sprachen L und K(L) ist rekursiv aufzählbar (aber nicht rekursiv), die andere ist nicht rekursiv aufzählbar.
