Entscheidungsproblem

Entscheidungsproblem.png Als Entscheidungsproblem bezeichnet man heute in der Theoretischen Informatik allgemein Probleme, für die zu einer gegebenen Eingabe als Lösung nur zwei Antworten (z. B. ja oder nein bzw. 1 oder 0 usw.) vorgesehen sind. Jedes derartige Problem lässt sich auch als das Wortproblem einer formalen Sprache auffassen. Deshalb wird auch häufig der Begriff (formale) Sprache anstelle von Entscheidungsproblem verwendet.

Ursprünglich galt als Entscheidungsproblem die Frage, ob es einen Algorithmus gibt, der für einen beliebigen Ausdruck in der Prädikatenlogik bestimmt, ob es sich um eine allgemeingültige Aussage handelt oder nicht. Dieses (spezielle) Entscheidungsproblem wurde 1928 von David Hilbert gestellt (siehe Hilbertprogramm). Alan Turing und Alonzo Church haben für das Problem 1936 festgestellt, dass es unlösbar ist (siehe Halteproblem).

Eine formale Sprache $\mathbf{\mathit{\,S\,}}$ ist entscheidbar (rekursiv entscheidbar), wenn ihre charakteristische Funktion berechenbar ist. Es gibt dann also eine berechenbare Funktion $\mathbf{\mathit{\,f\,}}$ , sodass für alle Wörter $\mathbf{\mathit{\,w\,}}$ über die Symbole der Sprache $\mathbf{\mathit{\,S\,}}$ gilt:

$f(w)=\begin{cases} 1, & {\textrm{wenn~}}w \in S\\ 0, & {\textrm{wenn~}}w \notin S\end{cases}$

Die Semi-Entscheidbarkeit (Rekursive Aufzählbarkeit) einer (formalen) Sprache $\mathbf{\mathit{\,S\,}}$ ist dadurch gekennzeichnet, dass ihre partielle (eingeschränkte) charakteristische Funktion berechenbar ist. Es gibt dann folglich eine berechenbare Funktion $\mathbf{\mathit{\,f^{0}\,}}$ , sodass für alle Wörter $\mathbf{\mathit{\,w\,}}$ über die Symbole der Sprache $\mathbf{\mathit{\,S\,}}$ gilt:

$f^{0}(w)=\begin{cases} 1, & {\textrm{wenn~}}w \in S\\ {\textrm{undefiniert}}, & {\textrm{wenn~}}w \notin S\end{cases}$

Siehe auch

Theoretische Informatik | Rekursionstheorie | Formale Sprachen | Wortexport

Decision problem | Entscheidungsproblem | Problème de la décision | Entscheidungsproblem | בעיית הכרעה

Gourt Home::Gourt :: Entscheidungsproblem

Siehe auch