Unentscheidbarkeit

Ein Problem ist unentscheidbar, wenn weder seine Wahrheit, noch seine Unwahrheit bewiesen werden kann, es entweder lösbar ist oder unlösbar. Jede getroffene Entscheidung führt zu einem Widerspruch.

Darunter werden nicht die Probleme verstanden, für die eine Lösung einfach nicht bekannt ist, da hier ja durchaus eine Entscheidung über die Lösbarkeit existiert.

Ein einfaches Beispiel für eine unentscheidbare Aussage ist die paradoxe Aussage 'Diese Aussage ist falsch'. Jeder Versuch, eine Entscheidung zu treffen (egal ob richtig oder falsch) führt sofort zu einem Widerspruch.

Speziell in der Mathematischen Logik finden sich diese Art Probleme in bestimmten Aussagen in Axiomensystemen. Ein Unentscheidbarkeitsproblem ist das Halteproblem von Turing-Maschinen der theoretischen Informatik, ein weiteres der Nachweis der Unvollständigkeit der Mathematik durch Gödels Unvollständigkeitssatz.

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