Rekursiv aufzählbar

Rekursiv 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

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:

  • 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

  • Rekursiv aufzählbare Sprache — In der theoretischen Informatik ist eine rekursiv aufzählbare Sprache oder semientscheidbare Sprache L dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus L akzeptiert, aber keine Wörter, die nicht in L liegen. Im Unterschied …   Deutsch Wikipedia

  • Rekursiv aufzählbare Menge — Als semi entscheidbare Menge (auch halb entscheidbare Menge) wird in der Berechenbarkeitstheorie eine Menge A bezüglich einer Grundmenge M bezeichnet, wenn ihre partielle charakteristische Funktion definiert durch berechenbar ist. Die Menge M… …   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

  • 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

  • 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

  • Semi-entscheidbare Sprache — Eine rekursiv aufzählbare Sprache oder semientscheidbare Sprache L ist dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus L akzeptiert, aber keine Wörter, die nicht in L liegen. Im Unterschied zu rekursiven Sprachen oder… …   Deutsch Wikipedia

  • Semientscheidbare Sprache — Eine rekursiv aufzählbare Sprache oder semientscheidbare Sprache L ist dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus L akzeptiert, aber keine Wörter, die nicht in L liegen. Im Unterschied zu rekursiven Sprachen oder… …   Deutsch Wikipedia

  • Projektionssatz (Informatik) — Der Projektionssatz ist ein hinreichendes Kriterium für eine Sprache, rekursiv aufzählbar zu sein. Eine Sprache ist rekursiv aufzählbar, wenn sie Definitionsbereich einer berechenbaren Funktion ist. Der Satz versteht sich als Rekursion, darum ist …   Deutsch Wikipedia

  • Axiomensystem — Ein Axiomensystem (auch: Axiomatisches System) ist ein System von grundlegenden Aussagen, Axiomen, die ohne Beweis angenommen und aus denen alle Sätze (Theoreme) des Systems logisch abgeleitet werden.[1][2] Die Ableitung erfolgt dabei durch die… …   Deutsch Wikipedia

Share the article and excerpts

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