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.

Definition

Eine Teilmenge der natürlichen Zahlen $S\; \backslash subseteq\; \backslash N$ 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 äquivalente dem Begriff der Berechenbarkeit zugrunde liegende Berechnungsmodelle nur abzählbar viele Eingaben zulassen, ist der Begriff für überabzählbare Mengen wie die reellen Zahlen nicht definiert. Es gibt jedoch Versuche, durch ein erweitertes Maschinenmodell den Begriff der Berechenbarkeit auch auf reelle Zahlen auszudehnen (z. B. das Blum-Shub-Smale-Modell).

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 für "ja" oder für "nein" gefordert wird, dass die Berechnung in endlicher Zeit anhält.

Theoretische Informatik

Recursive set | Komputebla aro | Ensemble récursif | קבוצה רקורסיבית | Insieme ricorsivo | 帰納的集合 | Zbiór rekurencyjny | 递归集合