Rekursiv aufzählbare Menge

Als rekursiv aufzählbare Menge (auch semi-entscheidbare Menge, positiv semi-entscheidbare Menge, halb-entscheidbare Menge, berechenbar aufzählbare Menge, kurz r.e., c.e.) wird in der Berechenbarkeitstheorie eine Menge von natürlichen Zahlen bezeichnet, wenn es einen Algorithmus gibt, der die Elemente dieser Menge aufzählt. Äquivalent ist diese Charakterisierung: Es gibt einen Algorithmus, der 1 ausgibt, wann immer die Eingabe ein Element der betreffenden Menge ist, und auf anderen Eingaben nie hält. Jede entscheidbare Menge ist rekursiv aufzählbar, aber es gibt rekursiv aufzählbare Mengen, die nicht entscheidbar sind.

Mengen von anderen Objekten als natürlichen Zahlen heißen rekursiv aufzählbar, wenn sie sich durch Gödelisierung in eine rekursiv aufzählbare Menge natürlicher Zahlen übersetzen lässt.

In der Literatur taucht gelegentlich der Begriff der berechenbaren Menge auf. Dieser Begriff wird uneinheitlich verwendet. Es können damit entscheidbare Mengen oder rekursiv aufzählbare Mengen gemeint sein.

Formale Definition

Formal werden rekursiv aufzählbare Mengen meist durch eine der folgenden, zueinander äquivalenten, Definitionen charakterisiert:

Rekursive Aufzählbarkeit

Eine Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M \subseteq \N} heiße rekursiv aufzählbar, falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = \emptyset} leer ist oder es eine totale, berechenbare Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \N \to M} gibt, deren Bild gerade Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ist.

Semi-Entscheidbarkeit

Die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} heiße semi-entscheidbar, wenn die partielle charakteristische Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi_M \colon \N \rightsquigarrow \{1\}} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} berechenbar ist.

Äquivalenzen zur Definition

Folgende Sätze sind untereinander äquivalent:

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ist rekursiv aufzählbar.
• $M$ ist semi-entscheidbar.
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ist vom Chomsky-Typ 0.
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ist die Menge aller Berechnungsergebnisse einer Turingmaschine.
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ist Definitionsbereich einer berechenbaren Funktion.
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ist Bildmenge einer berechenbaren Funktion.
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ist endlich oder Wertebereich einer injektiven berechenbaren Funktion.
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ist Bildmenge einer primitiv-rekursiven Funktion oder die leere Menge.
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} liegt in der Klasse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma^0_1} der arithmetischen Hierarchie.
• $M$ lässt sich many-one auf das Halteproblem reduzieren.
• Es gibt eine entscheidbare Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B \subseteq \N^2} für die gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in M \Leftrightarrow \exists y \colon (x;y) \in B} .

Eigenschaften

• Jede entscheidbare Menge ist rekursiv aufzählbar, aber es gibt rekursiv aufzählbare Mengen, die nicht entscheidbar sind.
• Eine Menge ist genau dann entscheidbar, wenn sie und ihr Komplement rekursiv aufzählbar sind.
• Jede endliche Menge ist rekursiv aufzählbar.
• Jede rekursiv aufzählbare Menge ist abzählbar, aber nicht alle abzählbaren Mengen sind rekursiv aufzählbar.
• Jede unendliche rekursiv aufzählbare Menge besitzt Teilmengen, die nicht rekursiv aufzählbar sind.
• Der Schnitt von endlich vielen rekursiv aufzählbaren Mengen ist rekursiv aufzählbar; die Vereinigung einer rekursiv aufzählbaren Menge von rekursiv aufzählbaren Mengen ist rekursiv aufzählbar. Es gibt rekursiv aufzählbare Mengen, deren Komplement nicht rekursiv aufzählbar ist.
• Eine partielle Funktion ist genau dann berechenbar, wenn ihr Graph rekursiv aufzählbar ist.

Beispiele

• Die Menge der Paare der Form: (Programm, Eingabe) mit der Eigenschaft: das Programm hält mit der Eingabe ist rekursiv aufzählbar. Diese Menge wird auch "Universelle Sprache" genannt. Damit ist das Halteproblem der Turingmaschinen semi-entscheidbar, denn man kann die gegebene Turingmaschine mit der gegebenen Eingabe laufen lassen und nach ihrer Terminierung 1 ausgeben. Das Komplement des Halteproblems ist nicht semi-entscheidbar.
• Die Selbstanwendbarkeit ist rekursiv aufzählbar: In obigem Beispiel beschränken wir uns auf die Eingaben, die dem jeweiligen Programm entsprechen.
• Das Äquivalenzproblem der Turingmaschinen ist nicht semi-entscheidbar. Auch das Komplement des Äquivalenzproblems ist nicht semi-entscheidbar.
• Die Werte der Busy-Beaver-Funktion sind nicht rekursiv aufzählbar.

Literatur

• Hartley Rogers: Theory of recursive functions and effective computability. McGraw-Hill, 1967.