Das Kefk Network Wiki befindet sich im Testbetrieb.
Rekursive Aufzählbarkeit
Aus Kefk.
(Weitergeleitet von Aufzählbare Menge)
Die rekursive Aufzählbarkeit ist ein Begriff aus der Berechenbarkeitstheorie. Er gibt Aufschluss darüber, ob sich die Elemente einer vorgegebenen Menge schrittweise von einem Computer erzeugen lassen.
Inhaltsverzeichnis |
Definition
Eine Menge M heißt rekursiv aufzählbar, falls sie leer ist, oder es eine surjektive berechenbare Funktion 
gibt.
Die Klasse der rekursiv aufzählbaren Mengen wird in der Literatur meist mit RE bezeichnet.
Äquivalenzen zur Definition
- M ist rekursiv aufzählbar
- M ist semi-entscheidbar
- M ist vom Typ 0
- M ist die Menge aller Berechnungsergebnisse einer Turingmaschine
- χ'M, die halbe charakteristische Funktion, ist Turing-, WHILE- oder GOTO-berechenbar
- M ist Definitionsbereich einer berechenbaren Funktion
- M ist Wertebereich einer berechenbaren Funktion
Eigenschaften
- Jede endliche Menge ist rekursiv aufzählbar.
- Eine Menge ist genau dann rekursiv aufzählbar, wenn sie semi-entscheidbar ist.
- Jede rekursiv aufzählbare Menge ist abzählbar.
- Nicht alle abzählbaren Mengen sind rekursiv aufzählbar.
- Jede unendliche rekursiv aufzählbare Sprache besitzt Teilmengen, die nicht rekursiv aufzählbar sind.
- Genau dann, wenn eine Menge und ihr Komplement rekursiv aufzählbar sind, dann ist sie bereits rekursiv entscheidbar.
Beispiele
- Die Menge der Paare der Form: (Programm, Eingabe) mit der Eigenschaft: das Programm hält mit der Eingabe ist rekursiv aufzählbar. (Siehe Halteproblem)
- Die Selbstanwendbarkeit ist rekursiv aufzählbar: In obigem Beispiel beschränken wir uns auf die Eingaben, die dem jeweiligen Programm entsprechen.
- Die Werte der Busy-Beaver-Funktion Σ(n) sind nicht rekursiv aufzählbar.
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Rekursive_Aufz%C3%A4hlbarkeit, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
