Rekursiv aufzählbare Sprache - Recursively enumerable language

In Mathematik , Logik und Informatik wird eine formale Sprache als rekursiv aufzählbar (auch erkennbar , teilweise entscheidbar , halbentscheidbar , Turing-akzeptabel oder Turing-erkennbar ) bezeichnet, wenn es sich um eine rekursiv aufzählbare Teilmenge in der Menge aller möglichen Wörter über dem Alphabet von handelt die Sprache, dh wenn es eine Turing-Maschine gibt, die alle gültigen Zeichenfolgen der Sprache auflistet.

Rekursiv aufzählbare Sprachen werden in der Chomsky-Hierarchie der formalen Sprachen als Typ-0- Sprachen bezeichnet. Alle regulären , kontextfreien , kontextsensitiven und rekursiven Sprachen sind rekursiv aufzählbar.

Die Klasse aller rekursiv aufzählbaren Sprachen heißt RE .

Definitionen

Es gibt drei äquivalente Definitionen einer rekursiv aufzählbaren Sprache:

1. Eine rekursiv aufzählbare Sprache ist eine rekursiv aufzählbare Teilmenge in der Menge aller möglichen Wörter über dem Alphabet der Sprache .
2. Eine rekursiv aufzählbare Sprache ist eine formale Sprache, für die es eine Turing-Maschine (oder eine andere berechenbare Funktion ) gibt, die alle gültigen Zeichenfolgen der Sprache auflistet. Beachten Sie, dass bei einer unendlichen Sprache der bereitgestellte Aufzählungsalgorithmus so gewählt werden kann, dass Wiederholungen vermieden werden, da wir testen können, ob die für die Zahl n erzeugte Zeichenfolge für eine Zahl, die kleiner als n ist, "bereits" erzeugt wurde . Wenn es bereits produziert wurde, verwenden Sie stattdessen die Ausgabe für die Eingabe n + 1 (rekursiv), aber testen Sie erneut, ob es "neu" ist.
3. Eine rekursiv aufzählbare Sprache ist eine formale Sprache, für die es eine Turing-Maschine (oder eine andere berechenbare Funktion) gibt, die angehalten und akzeptiert wird, wenn eine Zeichenfolge in der Sprache als Eingabe angezeigt wird, die jedoch entweder angehalten und abgelehnt oder für immer wiederholt werden kann, wenn eine Zeichenfolge angezeigt wird nicht in der Sprache. Vergleichen Sie dies mit rekursiven Sprachen , bei denen die Turing-Maschine in jedem Fall angehalten werden muss.

Alle regulären , kontextfreien , kontextsensitiven und rekursiven Sprachen sind rekursiv aufzählbar.

Der Satz von Post zeigt, dass RE zusammen mit seinem Komplement co-RE der ersten Ebene der arithmetischen Hierarchie entspricht .

Beispiel

Der Satz von Haltemaschinen ist rekursiv aufzählbar, aber nicht rekursiv. In der Tat kann man die Turing-Maschine ausführen und akzeptieren, wenn die Maschine anhält, daher ist sie rekursiv aufzählbar. Andererseits ist das Problem unentscheidbar.

Einige andere rekursiv aufzählbare Sprachen, die nicht rekursiv sind, umfassen:

• Problem mit der Postkorrespondenz
• Mortalität (Berechenbarkeitstheorie)
• Entscheidungsproblem

Verschlusseigenschaften

Recursively enumerable Sprachen (REL) sind geschlossen unter den folgenden Operationen. Das heißt, wenn L und P zwei rekursiv aufzählbare Sprachen sind, sind auch die folgenden Sprachen rekursiv aufzählbar:

• der Kleene-Stern von L.${\ displaystyle L ^ {*}}$
• die Verkettung von L und P.${\ displaystyle L \ circ P}$
• die Gewerkschaft ${\ displaystyle L \ cup P}$
• die Kreuzung . ${\ displaystyle L \ cap P}$

Rekursiv aufzählbare Sprachen werden nicht unter festgelegten Unterschieden oder Ergänzungen geschlossen. Die eingestellte Differenz - ist rekursiv aufzählbar, wenn sie rekursiv ist. Wenn rekursiv aufzählbar ist, dann ist das Komplement von genau dann rekursiv aufzählbar, wenn es auch rekursiv ist. ${\ displaystyle L}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle L}$${\ displaystyle L}$${\ displaystyle L}$

Verweise

• Sipser, M. (1996), Einführung in die Theorie der Berechnung , PWS Publishing Co .
• Kozen, DC (1997), Automata and Computability , Springer .

Externe Links

• Komplexitätszoo : Klasse RE
• Vorlesungsfolien