Rekursiv entscheidbare Menge

Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat oder nicht. Wenn es ein solches Entscheidungsverfahren nicht gibt, dann nennt man die Eigenschaft unentscheidbar. Als Entscheidungsproblem bezeichnet man die Frage, ob und wie für eine gegebene Eigenschaft ein Entscheidungsverfahren formuliert werden kann.^[1]

Während die wichtigsten syntaktischen Eigenschaften von Programmen entscheidbar sind, sind viele in der Praxis relevante semantische Eigenschaften von Programmen unentscheidbar, zum Beispiel die Terminierung von Programmen mit Eingaben (Halteproblem), oder die Funktionsgleichheit auf Programmen (Äquivalenzproblem).

Ursprünglich speziell für die Gültigkeit von Formeln gemeint, wird der Begriff inzwischen für beliebige Eigenschaften auf abzählbaren Mengen verwendet. Der Begriff des Algorithmus setzt ein Berechnungsmodell voraus; wenn nicht abweichendes gesagt wird, sind die Turingmaschinen oder ein gleichwertiges Modell gemeint.

Definition

Struktur eines Entscheidungsproblems

Eine Teilmenge T einer Menge M heißt entscheidbar, wenn ihre charakteristische Funktion $\chi_T: M\to \{0,1\}$ definiert durch

$\chi_T(t)=\begin{cases} 1, & {\textrm{falls~}}t \in T\\ 0, & {\textrm{sonst}}\end{cases}$

berechenbar ist. Der Entscheidbarkeitsbegriff ist somit auf den Berechenbarkeitsbegriff zurückgeführt.

Bei dieser Definition ist vorausgesetzt, dass alle Elemente der Menge M im Rechner dargestellt werden können. Die Menge M muss gödelisierbar sein. In der Theorie setzt man zum einfacheren Vergleich direkt $M=\mathbb{N}$ oder M = {0,1} ^* voraus. Im letzteren Fall hat man das Problem als das Wortproblem einer formalen Sprache dargestellt.

Da nur abzählbare Mengen gödelisierbar sind, 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).

Abgrenzung

Unentscheidbarkeit darf nicht verwechselt werden mit der praktischen oder fundamentalen Unmöglichkeit, einer Aussage einen Wahrheitswert zuzuordnen. Im Einzelnen geht es um folgende Begriffe:

1. Inkonsistenz: Paradoxien oder Antinomien zeigen, dass ein Kalkül Widersprüche enthält, also nicht widerspruchsfrei ist. Die Russellsche Antinomie zum Beispiel zeigte, dass die naive Mengenlehre Widersprüche enthält.
2. Unabhängigkeit: Aussagen, die zu einem widerspruchsfreien Kalkül hinzugenommen werden können, ohne einen Widerspruch zu erzeugen, heißen relativ widerspruchsfrei zu diesem Kalkül. Wenn auch deren Negation relativ widerspruchsfrei ist, dann ist die Aussage unabhängig. Zum Beispiel ist das Auswahlaxiom unabhängig von der Zermelo-Fraenkel-Mengenlehre.
3. Unvollständigkeit: In Kalkülen, die mindestens die Ausdrucksstärke der Arithmetik haben, gibt es wahre Aussagen, die nicht im Kalkül bewiesen werden können. Solche Kalküle nennt man unvollständig.

Entscheidbarkeit ist eine Eigenschaft von Prädikaten, und nicht von Aussagen. Das Prädikat ist dabei als wohldefiniert vorausgesetzt, es liefert also für jedes Element der Menge einen definierten Wahrheitswert. Unentscheidbarkeit besagt nur, dass das Prädikat nicht durch einen Algorithmus berechnet werden kann.

Aussagen als nullstellige Prädikate betrachtet sind immer entscheidbar, auch wenn ihr Wahrheitswert noch ungeklärt ist. Wenn die Aussage wahr ist, dann ist der Algorithmus, der immer Eins ausgibt ein Entscheidungsverfahren. Sonst ist der Algorithmus, der immer Null ausgibt, ein Entscheidungsverfahren.

Geschichte

Das Entscheidungsproblem ist „das Problem, die Allgemeingültigkeit von Ausdrücken festzustellen“ ^[2]. „Es handelt sich um das Problem, zu einer gegebenen deduktiven Theorie ein allgemeines Verfahren anzugeben, das uns die Entscheidung darüber gestattet, ob ein vorgegebener, in den Begriffen der Theorie formulierter Satz, innerhalb der Theorie bewiesen werden kann oder nicht.“^[3]

Entscheidend ist dabei, ob es ein rein mechanisch anzuwendendes Verfahren, einen Algorithmus, gibt, das in endlich vielen Schritten klärt, ob ein Ausdruck, eine Formel, in einem System gültig ist oder nicht.

Nach Frege/Whitehead/Russell war die „Kernfrage der Logiker und Mathematiker: Gibt es einen Algorithmus ..., der von einer beliebigen Formel eines logischen Kalküls feststellt, ob sie aus gewissen vorgegebenen Axiomen folgt oder nicht (das so genannte Entscheidungsproblem) ?“^[4]

Beispiele

Alle endlichen Mengen, die Menge aller geraden Zahlen und die Menge aller Primzahlen sind entscheidbar. Zu jeder entscheidbaren Menge ist auch sein Komplement entscheidbar. Zu zwei entscheidbaren Mengen sind deren Schnittmenge und deren Vereinigungsmenge entscheidbar.

Halteprobleme

Das Halteproblem für Turingmaschinen ist die Eigenschaft von Paaren von Turingmaschinen und Eingaben, dass die Turingmaschine für die Eingabe terminiert, das heißt nur endlich lange rechnet. Alan Turing zeigte, dass das Halteproblem für Turingmaschinen unentscheidbar ist. Auch das gleichmäßige Halteproblem für Turingmaschinen, nämlich die Eigenschaft von Turingmaschinen, für jede Eingabe schließlich zu halten, ist unentscheidbar.

Das Halteproblem für linear beschränkte Turingmaschinen ist hingegen entscheidbar.

Gültigkeit in der Aussagenlogik

Die Gültigkeit im Aussagenkalkül ist entscheidbar.^[5] Bekannt ist das Komplement dazu, das Erfüllbarkeitsproblem der Aussagenlogik. Ein Entscheidungsverfahren ist die Methode der Wahrheitstafeln.

Gültigkeit in der Prädikatenlogik

Das (spezielle) Entscheidungsproblem für die Prädikatenlogik wurde 1928 von David Hilbert gestellt (siehe Hilbertprogramm). Alan Turing und Alonzo Church haben für das Problem 1936 festgestellt, dass es unlösbar ist (siehe Halteproblem).

Das Entscheidungsproblem ist nicht für die allgemeine Prädikatenlogik^[6], sondern lediglich für einen Teilbereich der Prädikatenlogik, nämlich für die Prädikatenlogik "mit einstelligen Prädikaten 1. Stufe“^[7] gelöst.

Lösbarkeit Diophantischer Gleichungen

Eine Polynomgleichung nennt man diophantisch, wenn alle Koeffizienten ganzzahlig sind und nur ganzzahlige Lösungen gesucht werden. Die Eigenschaft von Diophantischen Gleichungen, eine Lösung zu haben (Hilberts zehntes Problem), ist unentscheidbar. Die Lösbarkeit von Linearen Diophantischen Gleichungen dagegen ist entscheidbar.

Das Postsche Korrespondenzproblem

Man nennt eine endliche Liste von Paaren nichtleerer Wörter über einem endlichen Alphabet einen Problemfall. Eine Lösung zu einem Problemfall ist eine nichtleere endliche Folge von Nummern für Wortpaare in der Liste, so dass die ersten Komponenten der Wortpaare zusammengesetzt das gleiche Wort ergeben wie die zweiten Komponenten der Wortpaare.

Beispiel: $\left(a,aba\right), (ab,bb), (baa,aa)$ hat die Lösung $\left(1,3,2,3\right)$, denn es gilt $a\cdot baa \cdot ab \cdot baa = abaaabbaa = aba \cdot aa \cdot bb \cdot aa$.

Das Postsche Korrespondenzproblem, das heißt die Eigenschaft von Problemfällen, eine Lösung zu besitzen, ist unentscheidbar.

Verwandte Begriffe

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. Wenn sowohl eine Menge als auch ihr Komplement semi-entscheidbar sind, dann ist die Menge entscheidbar. Das Halteproblem ist semi-entscheidbar, denn die Antwort "ja" kann immer gegeben werden durch Laufenlassen der Programms. Aber das Komplement des Halteproblems ist nicht semi-entscheidbar.

Siehe auch

• Berechenbarkeit
• Semi-entscheidbare Menge
• Äquivalenzproblem
• Endlichkeitsproblem
• Leerheitsproblem
• Postsches Korrespondenzproblem

Einzelnachweise

1. ↑ Regenbogen/Meyer, Wörterbuch der philosophischen Begriffe (2005)/entscheidbar
2. ↑ Hilbert/Ackermann, Grundzüge der theoretischen Logik, 6. Aufl. (1972), S. 119
3. ↑ Tarski, Einführung in die mathematische Logik, 5. Aufl. (1977), S. 145
4. ↑ Brandt/Dietrich/Schön, Sprachwissenschaft, 2. Aufl. (2006), S. 14
5. ↑ Hilbert/Ackermann, Grundzüge, 6. Aufl. (1972), S. 119
6. ↑ Quine, Grundzüge, 8. Aufl. (1993), S. 247
7. ↑ Czayka, Logik (1991), S. 45

Literatur

• Czayka, Logik (1991), S. 45 ff.
• Ausführlich Quine, Grundzüge, 8. Aufl. (1993), S. 142 ff.
• Hoyningen-Huene, Logik (1998), S. 226 ff.