Entscheidungsproblem

framed|Struktur eines Entscheidungsproblems 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 solche 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 Tautologie handelt oder nicht. Dieses (spezielle) Entscheidungsproblem wurde 1928 von David Hilbert gestellt (siehe Hilbertprogramm) und 1930 von Kurt Gödel negativ beantwortet (siehe Gödelscher Unvollständigkeitssatz). Zu dem gleichen Ergebnis kamen 1936 Alan Turing und Alonzo Church, die das Problem von einer völlig anderen Perspektive beleuchteten (siehe Halteproblem).

Eine formale Sprache \mathbf{\mathit{\,S\,}} ist entscheidbar (rekursiv), wenn es eine berechenbare Funktion \mathbf{\mathit{\,f\,}} gibt, sodass für alle Worte \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 es eine berechenbare Funktion \mathbf{\mathit{\,f^{0}\,}} gibt, sodass für alle Worte \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

See also: Entscheidungsproblem, 1928, 1930, 1936, Alan Turing, Algorithmus, Alonzo Church, Berechenbarkeit, Charakteristische Funktion, David Hilbert