Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

Eine Aussage ist unentscheidbar, wenn weder ihre Wahrheit, noch ihre Unwahrheit bewiesen werden kann.

Darunter werden nicht die Aussagen verstanden, für die eine Lösung einfach nicht bekannt ist, da hier durchaus eine Entscheidung über die Lösbarkeit existieren kann. In vielen Fällen weiß man von der Lösbarkeit, kennt aber die Lösung nicht.
Einfache Beispiele für unentscheidbare Aussagen sind Paradoxien wie z.B. 'Diese Aussage ist falsch' oder das Barbier-Paradoxon. Jeder Versuch, eine Entscheidung zu treffen (egal ob richtig oder falsch) führt sofort zu einem Widerspruch.

Interessanter wird es, wenn wir Aussagen in Theorien suchen, die dort nicht entscheidbar sind. So stellt sich heute die Mathematik weitgehend als eine Theorie dar, die mit dem Axiomensystem von Zermelo und Fraenkel plus Auswahlaxiom (ZFC) bewiesen werden kann. Eine Aussage, die hierin unentscheidbar ist, heißt dann auch unabhängig von diesem System. Solche Aussagen können wir dann je nachdem, ob wir ihnen Glauben schenken, hinzunehmen bzw. negiert hinzunehmen. Die so entstandene Mathematik besitzt ebenfalls wieder unentscheidbare Aussagen. Diese Beobachtung stammt von Kurt Gödel, siehe Gödelscher Unvollständigkeitssatz.

Ein Entscheidungsproblem ist unentscheidbar, wenn es kein algorithmisches Verfahren gibt, dieses zu entscheiden.
Ein Entscheidungsproblem stellt sich uns als eine Menge von Aufgabenstellungen dar, die wir mit einem auf dieses Problem zugeschnittenen Verfahren entscheiden wollen. Ein solches Problem ist unentscheidbar, wenn es sich dieser Problemlösung entzieht, d.h. es kein allgemeines Verfahren gibt, um es zu lösen. Nicht entscheidbar und unentscheidbar werden manchmal als Synonyme verwendet. Mit der Church-Turing-These genügt es nach einem Programm einer Turing-mächtigen Programmiersprache zu suchen.

Beispiele für nicht entscheidbare Entscheidungsprobleme sind:

1. Das Halteproblem von Turing-Maschinen.
2. Das Problem, welche Turingmaschine nicht hält, wenn eine Kodierung ihrer selbst auf dem Eingabeband steht. (Diagonalsprache)
3. Die Frage nach der Lösbarkeit der Diophantischen Gleichungen.
4. Das Busy-Beaver-Problem: Es ist zu entscheiden, ob für eine Zahl gilt: Gibt es eine Zahl , so dass Σ(n) = k gilt?
5. Das Postsche Korrespondenzproblem.

Einige Probleme, die nicht entscheidbar sind, sind immerhin noch semi-entscheidbar: So können wir zwar nicht sagen, wie lange wir für eine Ja-Antwort benötigen, aber wissen dennoch, dass jede Ja-Antwort schließlich von dem Semi-Entscheider produziert wird. Für Nein-Antworten ist hier keine Aussage möglich. Für das erste, das dritte und das fünfte Beispiel gibt es Semi-Entscheider. Das zweite und vierte Beispiel ist nicht entscheidbar. Ausführlicher wird das diskutiert unter arithmetische Hierarchie.

Wenn wir anstelle einer Entscheidung Werte berechnen wollen, kommen wir hier zu dem allgemeineren Begriff der Nicht-Berechenbarkeit.

Siehe auch: Prädikatenlogik, Semi-Entscheidbarkeit, Entscheidbarkeit

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Unentscheidbarkeit, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.