## [Entscheidbarkeit](/de/node/59956) Definition 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 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 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 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 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 Umkehrung Unentscheidbarkeit: Es existiert kein Algorithmus, der stets terminiert und die Zugehörigkeit für jede Eingabe korrekt entscheidet. ## Abgrenzung 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 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 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.