Ein Entscheidungsproblem ist entscheidbar, wenn es einen Algorithmus gibt, der für jede Eingabe nach endlicher Zeit korrekt Ja oder Nein ausgibt.