Entscheidungsproblem

Ein Problem was nur Ja oder Nein zurück gibt.

Für Maschinen:

$L_{entscheidbar}=\{L(M)|M\text{ ist TM und entscheidet in endlicher Zeit ob }w\in L(M)\text{ oder }w\notin L(M)\}$

Wortproblem = Entscheidungsproblem ob ein Wort in der Sprache ist.

siehe
semi-entscheidbar