Unentscheidbare

Unentscheidbare Probleme sind Entscheidungsprobleme, für die kein Algorithmus existiert, der für alle Eingaben in endlicher Zeit die korrekte Ja-/Nein-Antwort liefert. Formal bedeutet dies: Ein Problem ist decidierbar, wenn es eine Turing-Maschine gibt, die bei jeder Eingabe hält und die richtige Antwort ausgibt. Ist dies nicht der Fall, spricht man von Unentscheidbarkeit. Einige Probleme sind jedoch semi-entscheidbar (rekursiv aufzählbar): Es existiert eine Turing-Maschine, die alle Ja-Instanzen akzeptiert, während Nein-Instanzen möglicherweise nicht stoppen.

Zu den bekanntesten unentscheidbaren Problemen gehören das Halteproblem, das entscheidet, ob ein gegebenes Programm auf einer gegebenen Eingabe stoppt. Das Halteproblem ist semi-entscheidbar, aber nicht entscheidbar. Weiterhin ist das Entscheidungsproblem der ersten Ordnunglogik (Gültigkeit von Formeln) unentscheidbar (Church-Turing). Das Diophantische Gleichungsproblem, bekannt als Hilberts zehnte Aufgabe, ist ebenfalls unentscheidbar. Das Post-Korrespondenzproblem gehört ebenfalls zu den klassischen Beispielen. Der Rice’sche Satz (Theorem) besagt, dass jede nichttriviale semantische Eigenschaft von Programmen unentscheidbar ist.

Die Unentscheidbarkeit hat grundlegende Folgen für die Theorie der Berechenbarkeit. Sie grenzt ab, welche Fragen algorithmisch lösbar sind, und motiviert die Untersuchung von beschränkten oder speziellen Teilgebieten, in denen Probleme decidierbar oder zumindest semidecidierbar bleiben. In der Praxis führt dies dazu, dass man in vielen Bereichen auf Teilprobleme, ineffiziente Heuristiken oder formale Beschränkungen zurückgreift, um praktikable Antworten zu erhalten.