Aufzählbarkeit

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 es eine surjektive, berechenbare Funktion \mathbb{N} \to M gibt. Die leere Menge ist rekursiv aufzählbar.

Eine Menge von Zahlen M = S1,S2,..., ist dann aufzählbar, wenn es eine Funktion f(x) gibt, die alle Elemente von M berechnen kann (f(1) = S1, f(2) = S2,...).

Die Klasse der rekursiv aufzählbaren Mengen wird in der Literatur meist mit RE (vom englischen Recursively Enumerable) bezeichnet.

Äquivalenzen zur Definition

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, aber 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.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Rekursive Aufzählbarkeit — 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 1 Definition 2… …   Deutsch Wikipedia

  • Partielle charakteristische Funktion — Die halbe charakteristische Funktion oder partielle charakteristische Funktion ist eine Funktion der Mathematik, die eine Menge identifiziert. Sie ist folgendermaßen definiert: χ A : A → {1}, a → 1. Wie man sehen kann, steckt die ganze „Magie“… …   Deutsch Wikipedia

  • Abzählbar — In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • Abzählbar unendlich — In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • Abzählbare Menge — In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • Akzeptieren (Automaten- und Komplexitätstheorie) — Die Begriffe Akzeptieren und Entscheiden sind in der Automaten und Komplexitätstheorie für viele in ihrer Wahrnehmung annähernd gleich. Sie sind es aber nicht genau. Aus diesem Wahrnehmungsunterschied haben Mathematiker folgenden formalen… …   Deutsch Wikipedia

  • Aufzählbar — 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 1 Definition 2… …   Deutsch Wikipedia

  • 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 1 Definition 2… …   Deutsch Wikipedia

  • Berechenbar — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Berechenbare Folge — Eine Folge heißt genau dann berechenbar, wenn es eine berechenbare Funktion gibt mit f(i) = ai. Siehe auch: Rekursive Aufzählbarkeit, Berechenbarkeit Kategorie: Berechenbarkeitstheorie …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”