Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 15. August 2020 

Entscheidungsproblem


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Das Entscheidungsproblem ist die Frage ob es einen gibt der für einen beliebigen Ausdruck in Prädikatenlogik bestimmt ob es sich um eine Tautologie (Logik) handelt oder nicht. Das Entscheidungsproblem wurde 1928 von David Hilbert gestellt und 1936 von Alan Turing und Alonzo Church negativ beantwortet.

Allgemeiner bezeichnet man in der Theoretischen Informatik Probleme für die zu einer gegebenen als Lösung nur zwei Antworten (z. B. ja oder nein bzw. 0 oder 1 usw.) vorgesehen sind als Entscheidungsproblem. Jedes Problem lässt sich als das Wortproblem einer formalen Sprache auffassen.

Ein formale Sprache S ist entscheidbar wenn es eine berechenbare Funktion f gibt sodass für alle Worte W über die Symbole der Sprache S gilt:

  • f ( W ) = 1 genau dann wenn W in S liegt.
  • f ( W ) = 0 genau dann wenn W nicht in S liegt.

Die Semientscheidbarkeit einer (formalen) Sprache S ist dadurch gekennzeichnet dass es eine Funktion f ° gibt sodass für alle Worte W über die Symbole der Sprache S gilt:

  • f °( W ) = 1 genau dann wenn W in S liegt.
  • f °( W ) nicht definiert wenn W nicht in S liegt.

Siehe auch



Bücher zum Thema Entscheidungsproblem

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Entscheidungsproblem.html">Entscheidungsproblem </a>