In der Mathematik, Logik und Informatik, wird eine formelle Sprache rekursiv enumerable genannt (auch erkennbar, teilweise entscheidbar oder Turing-annehmbar), wenn es rekursiv enumerable Teilmenge im Satz aller möglichen Wörter über das Alphabet der Sprache ist, d. h., wenn dort eine Maschine von Turing besteht, die alle gültigen Schnuren der Sprache aufzählen wird.

Rekursiv sind Enumerable-Sprachen als Sprachen des Typs 0 in der Hierarchie von Chomsky von formellen Sprachen bekannt. Alle regelmäßigen, mit dem Zusammenhang empfindlichen und rekursiven Sprachen ohne Zusammenhänge sind rekursiv enumerable.

Die Klasse von allen rekursiv enumerable Sprachen wird RE genannt.

Definitionen

Dort bestehen Sie drei gleichwertige Hauptdefinitionen für das Konzept rekursiv enumerable Sprache.

1. Rekursiv enumerable Sprache ist rekursiv enumerable Teilmenge im Satz aller möglichen Wörter über das Alphabet der Sprache.
2. Rekursiv enumerable Sprache ist eine formelle Sprache, für die dort eine Maschine von Turing besteht (oder andere berechenbare Funktion), der alle gültigen Schnuren der Sprache aufzählen wird. Bemerken Sie, dass, wenn die Sprache unendlich ist, der zur Verfügung gestellte Aufzählen-Algorithmus gewählt werden kann, so dass es Wiederholungen vermeidet, da wir prüfen können, ob die für die Nummer n erzeugte Schnur "bereits" für eine Zahl erzeugt wird, die weniger ist als n. Wenn es bereits erzeugt wird, verwenden Sie die Produktion für den Eingang n+1 stattdessen (rekursiv), aber wieder, prüfen Sie, ob es "neu" ist.
3. Rekursiv enumerable Sprache ist eine formelle Sprache, für die dort eine Maschine von Turing besteht (oder andere berechenbare Funktion), der hinken und wenn geboten, jede Schnur auf der Sprache, wie eingegeben, akzeptieren wird, aber entweder halten und zurückweisen kann oder Schleife, für immer wenn geboten, eine Schnur nicht auf der Sprache. Stellen Sie dem in rekursive Sprachen gegenüber, die verlangen, dass die Maschine von Turing in allen Fällen hinkt.

Alle regelmäßigen, mit dem Zusammenhang empfindlichen und rekursiven Sprachen ohne Zusammenhänge sind rekursiv enumerable.

Der Lehrsatz des Postens zeigt, dass RE, zusammen mit seinem Ergänzungskern, dem ersten Niveau der arithmetischen Hierarchie entsprechen.

Verschluss-Eigenschaften

Rekursiv werden Enumerable-Sprachen unter den folgenden Operationen geschlossen. D. h. wenn L und P zwei rekursiv enumerable Sprachen sind, dann sind die folgenden Sprachen rekursiv enumerable ebenso:

• der Stern von Kleene von L
• die Verkettung von L und P
• die Vereinigung
• die Kreuzung

Bemerken Sie, dass rekursiv enumerable Sprachen unter dem Satz-Unterschied oder der Fertigstellung nicht geschlossen werden. Der Satz-Unterschied L - P kann oder kann nicht rekursiv enumerable sein. Wenn L rekursiv enumerable ist, dann ist die Ergänzung von L rekursiv enumerable, wenn, und nur wenn L auch rekursiv ist.

Außenverbindungen

• Vortrag lässt gleiten
• Sipser, M. (1996), Einführung in die Theorie der Berechnung, PWS Publishing Co.
• Kozen, D.C. (1997), Automaten und Berechenbarkeit, Springer.