Diskussion:Entscheidungsproblem

Eine mögliche Redundanz der Artikel Entscheidungsproblem, Rekursiv entscheidbare Menge und Unentscheidbarkeit wurde von Mai 2008 bis Juni 2008 diskutiert (zugehörige Redundanzdiskussion). Bitte beachte dies vor der Anlage einer neuen Redundanzdiskussion.

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)

Ein paar Beispiele wären toll. --134.93.142.246 Diskussion:Entscheidungsproblem#c-134.93.142.246-2006-12-07T13:25:00.000Z-Beispiele11Beantworten

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 Diskussion:Entscheidungsproblem#c-AlfonsGeser-2008-05-10T13:37:00.000Z-Beispiele11Beantworten