Entscheidbarkeit

Struktur eines Entscheidungsproblems

Eine Teilmenge ${\displaystyle T}$ einer abzählbaren Menge ${\displaystyle M}$ heißt entscheidbar, wenn ihre charakteristische Funktion ${\displaystyle \chi _{T}\colon M\to \{0,1\}}$ definiert durch

${\displaystyle \chi _{T}(t)={\begin{cases}1,&{\text{falls }}t\in T\\0,&{\text{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 ${\displaystyle M}$ im Rechner dargestellt werden können. Die Menge ${\displaystyle M}$ muss gödelisierbar sein. In der Theorie setzt man zum einfacheren Vergleich direkt ${\displaystyle M=\mathbb {N} }$ oder ${\displaystyle 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).

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 konsistenten 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.

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 und 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]

Kurt Gödel veröffentlichte 1931 ein Werk zum Entscheidungsproblem; der Brite Alan Turing (1912–1954) formulierte in seiner für diesen Zweig der Mathematik grundlegenden Arbeit On Computable Numbers, with an Application to the “Entscheidungsproblem” (28. Mai 1936) Gödels Ergebnisse von 1931 neu. Er ersetzte dabei Gödels universelle, arithmetisch-basierte formale Sprache durch einfache, formale Geräte, die als Turingmaschine bekannt wurden.

Der Logiker Heinrich Scholz (1884–1956) erbat (und erhielt) von Turing 1936 ein Exemplar dieser Arbeit.[5] Auf Basis dieser Arbeit hielt Scholz (laut Achim Clausing) „das weltweit erste Seminar über Informatik“.

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

Eine allgemeinere Klasse als die entscheidbaren Mengen sind die rekursiv aufzählbaren oder semi-entscheidbaren Mengen, bei denen lediglich für „ja“ 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 durch Laufenlassen des Programms gegeben werden. Das Komplement des Halteproblems ist jedoch nicht semi-entscheidbar.

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

• Lothar Czayka: Formale Logik und Wissenschaftsphilosophie. Einführung für Wirtschaftswissenschaftler. Oldenbourg, München u. a. 1991, ISBN 3-486-20987-6, S. 45 ff.
• Willard Van Orman Quine: Grundzüge der Logik. 8. Auflage. Suhrkamp, Frankfurt am Main 1993, ISBN 3-518-27665-4, S. 142 ff. (Suhrkamp-Taschenbuch Wissenschaft 65), ausführlich.
• Paul Hoyningen-Huene: Formale Logik. Eine philosophische Einführung. Reclam, Stuttgart 1998, ISBN 3-15-009692-8, S. 226 ff. (Reclams Universal-Bibliothek 9692)
• Hartley Rogers: Theory of recursive functions and effective computability. McGraw-Hill, 1967.
• Uwe Schöning: Theoretische Informatik – kurzgefasst. 4. Auflage. Spektrum, 2000, ISBN 3-8274-1099-1, S. 122 ff.

1. Arnim Regenbogen, Uwe Meyer (Hrsg.): Wörterbuch der philosophischen Begriffe. Sonderausgabe. Meiner, Hamburg 2006, ISBN 3-7873-1761-9, „entscheidbar“.
2. David Hilbert, W. Ackermann: Grundzüge der theoretischen Logik. 6. Auflage. Springer, Berlin u. a. 1972, ISBN 0-387-05843-5, S. 119 (Die Grundlehren der mathematischen Wissenschaften 27).
3. Alfred Tarski: Einführung in die mathematische Logik. 5. Auflage, erweitert um den Beitrag „Wahrheit und Beweis“. Vandenhoeck & Ruprecht, Göttingen 1977, ISBN 3-525-40540-5, S. 145 (Moderne Mathematik in elementarer Darstellung 5).
4. Patrick Brandt, Rolf-Albert Dietrich, Georg Schön: Sprachwissenschaft. Ein roter Faden für das Studium der deutschen Sprache. 2. überarbeitet und aktualisierte Auflage. Böhlau, Köln u. a. 2006, ISBN 3-412-00606-8, S. 14 (UTB 8331).
5. Das Exemplar wurde am Institut für Informatik der Westfälischen Wilhelms-Universität in Münster von Achim Clausing gefunden (Westfälische Nachrichten. 28. Januar 2013: Auf den Spuren eines Pioniers: In der Unibibliothek Münster liegen Originaldrucke des Informatikers Alan Turing; online).
6. Hilbert/Ackermann: Grundzüge. 6. Auflage. (1972), S. 119.
7. Willard Van Orman Quine: Grundzüge der Logik. 8. Auflage. Suhrkamp, Frankfurt am Main 1993, ISBN 3-518-27665-4, S. 247.
8. Lothar Czayka: Formale Logik und Wissenschaftsphilosophie. Einführung für Wirtschaftswissenschaftler. Oldenbourg, München u. a. 1991, ISBN 3-486-20987-6, S. 45.
9. Cubitt, Perez-Garcia, Wolf: Undecidability of the spectral gap, Nature, Band 528, 2015, S. 207, Arxiv Preprint