Diskussion:Entscheidungsproblem

David Hilbert hat meines Wissens nach das Entscheidungsproblem bereits 1900 in Paris auf der Mathematikertagung anlässlich der dortigen Weltausstellung vorgestellt. Wer weiß auf welche Quelle sich die Angabe 1928 bezieht?

Gruß --Gerhard Buntrock 12:59, 11. Aug 2005 (CEST)

Beispiele

Ein paar Beispiele wären toll. --134.93.142.246 14:25, 7. Dez. 2006 (CET)

Noch besser: Drei Listen von Beispielen. Die eine Liste sollte entscheidbare Probleme anführen, die zweite unentscheidbare, die dritte ungelöste. Skizze:

Entscheidbare Probleme: Erfüllbarkeitsproblem für aussagenlogische Formeln (SAT), Wortproblem für nicht-verkürzende Sprachen, Äquivalenzproblem (und weitere Probleme) für reguläre Grammatiken

Unentscheidbare Probleme: Halteproblem der Turingmaschinen, Postsches Korrespondenzproblem, Äquivalenzproblem für kontextfreie Grammatiken

Probleme, deren Entscheidbarkeit noch offen ist: Äquivalenzproblem für deterministisch kontextfreie Grammatiken (?)

Diese beiden Listen sollten nicht unübersichtlich werden. Deshalb sollten nur die bekanntesten und bedeutendsten Probleme aufgeführt werden.

Die Unterscheidung in Mathematik/Logik und Informatik kommt mir künstlich vor. Gehört denn die Logik nicht auch zur Informatik? Die beiden Teile sollten zusammengeführt werden.--AlfonsGeser 15:37, 10. Mai 2008 (CEST)