Eigenschaft eines Entscheidungsproblems, dass es ein effektives (algorithmisches) Verfahren im gewählten Rechenmodell gibt, das immer terminiert und korrekt entscheidet, ob eine Eingabe zur Sprache gehört.

Prinzip

Ein Problem ist entscheidbar genau dann, wenn es eine terminierende mechanische Methode gibt, die für jede Instanz Ja/Nein liefert; Entscheidbarkeit ist unter booleschen Operationen abgeschlossen, sofern effektive Konstruktionen vorliegen.

Demonstration

Die Menge der von einem deterministischen endlichen Automaten akzeptierten Wörter ist entscheidbar, weil der Übergangsalgorithmus die Eingabe liest, terminiert und Akzeptanz oder Ablehnung liefert.

Fehlanwendung

Eine Semi-Entscheidungsprozedur (die nur bei positiven Instanzen hält) fälschlich als vollständiges Entscheidungsverfahren zu werten oder aus der Lösbarkeit vieler praktischer Fälle auf einen allgemein haltenden Algorithmus zu schließen.

Konsequenz

Ist ein Problem entscheidbar, so lässt sich ein allgemeiner Algorithmus zur Klassifikation von Instanzen konstruieren; Komplement, Schnitt und Vereinigung entscheidbarer Sprachen bleiben entscheidbar mit effektiven Konstruktionen.

Umkehrung

Unentscheidbarkeit: Es existiert kein Algorithmus, der stets terminiert und die Zugehörigkeit für jede Eingabe korrekt entscheidet.

Abgrenzung

Gilt für Entscheidungsprobleme, die in einem präzisen Rechenmodell (typischerweise Turingmaschinen) kodiert sind; umfasst nicht Ressourcenbeschränkungen, probabilistische Approximationen oder semantische Unabhängigkeit von Axiomensystemen.

Semantische Spannung

Wird oft mit Berechenbarkeit in polynomialer Zeit (Traktabilität) oder mit syntaktischer Vollständigkeit verwechselt; Entscheidbarkeit betrifft nur die Existenz eines haltenden, korrekten Verfahrens, nicht dessen Effizienz oder beweistheoretischen Status.

Synthese

Entscheidbarkeit bezeichnet die Klasse von Problemen, für die ein effektiver, haltender Algorithmus existiert, und grenzt damit exakte algorithmische Lösbarkeit von schwächeren Konzepten wie Semientscheidbarkeit oder Komplexitätsfragen ab.