Als Entscheidungsproblem bezeichnet man in der Theoretischen Informatik Probleme, für die zu einer gegebenen Eingabe als Lösung nur zwei Antworten (z. B. ja oder nein bzw. 0 oder 1 usw.) vorgesehen sind. Jedes Entscheidungsproblem lässt sich als das Wortproblem einer formalen Sprache auffassen.
Ein formale Sprache S ist entscheidbar, wenn es eine berechenbare Funktion f gibt, sodass für alle Worte W über die Symbole der Sprache S gilt:
- f(W) = 1 genau dann wenn W in S liegt.
- f(W) = 0 genau dann wenn W nicht in S liegt.
Die Semientscheidbarkeit einer (formalen) Sprache S ist dadurch gekennzeichnet, dass es eine berechenbare Funktion f° gibt, sodass für alle Worte W über die Symbole der Sprache S gilt:
- f°(W) = 1 genau dann wenn W in S liegt.
- f°(W) nicht definiert wenn W nicht in S liegt.
Siehe auch
