Rekursiv entscheidbare Menge

aus Wikipedia, der freien Enzyklopädie

Eine Menge heißt rekursiv entscheidbar oder einfach entscheidbar, wenn es einen Algorithmus gibt, der nach endlicher Zeit terminiert und entscheidet, ob die Eingabe zur Menge gehört oder nicht.

[Bearbeiten] Definition

Eine Menge heißt entscheidbar gdw. die charakteristische Funktion der Menge (dies ist eine totale Funktion!) berechenbar ist.

Eine Teilmenge der natürlichen Zahlen heißt entscheidbar, wenn es eine totale berechenbare Funktion f gibt mit

.

Über Bijektionen zu den natürlichen Zahlen kann auch die Entscheidbarkeit von Teilmengen anderer abzählbarer Mengen wie etwa der rationalen Zahlen definiert werden.

Da Turingmaschinen und (bezüglich des Begriffes der Berechenbarkeit) äquivalente Berechnungsmodelle nur abzählbar viele Eingaben zulassen, ist der Begriff der Entscheidbarkeit für überabzählbare Mengen wie die der reellen Zahlen nicht definiert. Es gibt jedoch Versuche, durch ein erweitertes Maschinenmodell den Begriff der Berechenbarkeit auf reelle Zahlen auszudehnen (z.B. das Blum-Shub-Smale-Modell).

[Bearbeiten] Beispiele

Alle endlichen Mengen, Komplemente endlicher Mengen, die Menge aller geraden Zahlen und die Menge aller Primzahlen sind entscheidbar. Nicht entscheidbar ist die Menge aller (durch Gödelnummern kodierten) Turingmaschinen, die immer halten (Halteproblem).

Eine allgemeinere Klasse als die entscheidbaren Mengen sind die rekursiv aufzählbaren oder semi-entscheidbaren Mengen, bei denen lediglich entweder nur für "ja" oder nur für "nein" gefordert wird, dass die Berechnung in endlicher Zeit anhält.