##  [Unentscheidbarkeit](/de/node/59958) 

 Definition

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

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

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

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

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

Umkehrung

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

 

 

 

 

 





## Abgrenzung

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

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

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.