Entscheidbar

Aus AnthroWiki
Wechseln zu: Navigation, Suche
Die logische Struktur eines Entscheidungsproblems

Eine Eigenschaft auf einer Menge heißt entscheidbar oder rekursiv ableitbar, wenn es ein Entscheidungsverfahren gibt, durch das sich für jedes Element der Menge feststellen lässt, ob es diese Eigenschaft hat oder nicht; andernfalls nennt man die Eigenschaft unentscheidbar. Das Entscheidungsproblem besteht in der Frage, ob ein geeigneter Algorithmus für das Entscheidungsverfahren gefunden werden kann.

Mathematisch wird die Entscheidbarkeit auf die Berechenbarkeit des Entscheidungsverfahrens zurückgeführt:

Eine Teilmenge LaTeX: T einer abzählbaren Menge LaTeX: M heißt entscheidbar, wenn ihre charakteristische Funktion LaTeX: \chi_T\colon M\to \{0,1\} definiert durch

LaTeX: \chi_T(t)=\begin{cases} 1, & \mbox{falls t} \in T\\ 0, & {\textrm{sonst}}\end{cases}

berechenbar ist.