Entscheidungsproblem

Entscheidungsproblem bezeichnet die Frage, ob es für jede gegebene Aussage der ersten Ordnung eine allgemeine mechanische Entscheidungsprozedur gibt, die zuverlässig bestimmt, ob die Aussage gültig ist (in allen Interpretationen wahr) oder ob sie sich als widersprüchlich erweist. Der Begriff entstand im Kontext von Hilberts Programm in den späten 1920er Jahren, das eine einheitliche, algorithmische Methode suchte, um die Wahrheit mathematischer Aussagen zu entscheiden.

Hilberts Programm strebte eine vollständige und konsistente Formalisierung der Mathematik an, begleitet von einer einzigen Entscheidungsprozedur, die alle mathematischen Fragen lösen könne. Die Idee stieß jedoch an fundamentale Grenzen: Gödel zeigte 1931, dass in jedem hinreichend starken formalen System wahrheitsgetäuschte Aussagen existieren, die dort weder bewiesen noch widerlegt werden können, wodurch ein vollständiges Beweisverfahren ausgeschlossen wurde. Kurz darauf rückt die Frage nach einer universellen Entscheidungsprozedur für die erste Ordnung in den Fokus.

1936 bewies Alonzo Church, dass das Entscheidungsproblem für die erste Ordung unentscheidbar ist: Es gibt keinen allgemeinen Algorithmus, der für jedes erstes-ordnungslogische Satz die Gültigkeit decide. Informell unabhängig davon zeigte 1937 Alan Turing, mithilfe des Konzepts der Turing-Maschine, ähnliche Ergebnisse und legte damit die Verbindung zwischen Berechenbarkeit und Logik weiter fest. Die Church–Turing-Ergebnisse bedeuten, dass Hilberts Vision einer vollständigen, mechanischen Entscheidungsregel für die gesamte Mathematik unmöglich bleibt.

Heute ist die Unentscheidbarkeit des Entscheidungsproblems ein grundlegendes Ergebnis der Logik und der Berechenbarkeit. Zugleich gibt es decidierbare Teilbereiche, etwa die propositionale Logik oder bestimmte Theorien, in denen stabile Entscheidungsverfahren existieren.