In der
theoretischen Informatik heißt eine Eigenschaft auf einer Menge
entscheidbar (auch
rekursiv,
rekursiv ableitbar), wenn es ein
Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein
Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat oder nicht. Wenn es
kein solches Entscheidungsverfahren gibt, dann nennt man die Eigenschaft
unentscheidbar. Als
Entscheidungsproblem bezeichnet man die Frage, ob und wie für eine gegebene Eigenschaft ein Entscheidungsverfahren formuliert werden kann.