Eigenschaft eines Entscheidungsproblems, dass es keinen Algorithmus im gewählten Rechenmodell gibt, der für jede Eingabe stets terminiert und die Zugehörigkeit korrekt entscheidet.

Prinzip

Unentscheidbarkeit wird bewiesen, indem gezeigt wird, dass jeder angenommene Entscheider ein bereits unentscheidbares Problem lösen würde oder zu einem Widerspruch führt, typischerweise mittels Reduktion, Diagonalisierung oder Invarianzargumenten.

Demonstration

Das Halteproblem für Turingmaschinen ist unentscheidbar: Es gibt keine Turingmaschine, die für jedes kodierte Programm und Eingabe entscheidet, ob das Programm anhält.

Fehlanwendung

Eine offene Forschungsfrage als 'unentscheidbar' zu bezeichnen, wenn man eigentlich 'bisher unent-schieden' meint, oder Unentscheidbarkeit mit logischer Unabhängigkeit innerhalb eines Axiomensystems zu verwechseln.

Konsequenz

Ist ein Problem unentscheidbar, so existiert kein allgemein haltender Algorithmus; praktische Strategien müssen auf Semi-Entscheidungsverfahren, eingeschränkte Instanzen, Heuristiken oder zusätzliche Annahmen zurückgreifen.

Umkehrung

Entscheidbarkeit: Existenz eines Algorithmus, der stets terminiert und die Zugehörigkeit für alle Instanzen korrekt entscheidet.

Abgrenzung

Bezieht sich auf Entscheidungsprobleme in einem festen formalen Rechenmodell; bedeutet nicht, dass einzelne Instanzen nicht lösbar sind oder dass nützliche partielle Methoden unmöglich wären.

Semantische Spannung

Nahe der Idee logischer Unabhängigkeit (eine Aussage ist weder beweis- noch widerlegbar aus Axiomen), aber verschieden: Unentscheidbarkeit betrifft algorithmische Unmöglichkeit, Unabhängigkeit die deduktive Reichweite einer Theorie.

Synthese

Unentscheidbarkeit kennzeichnet die Grenzen algorithmischer Lösbarkeit: Sie tritt auf, wenn kein haltendes einheitliches Verfahren die Zugehörigkeit entscheidet, und zwingt zur Nutzung schwächerer Methoden oder zur Neufassung des Problems.