Diskussion:Wortproblem (Berechenbarkeitstheorie)

Ich glaube, das das Wortproblem für Typ 2 Grammatiken nich in quadratischer Zeit entscheidbar ist. Schliesslich ist es, wie der Autor selbst sagt auf den CYK Algorithmus zurückzuführen und dieser hat kubische Laufzeit, damit und auch laut dem mir vorliegenden Buch ist es kubische Laufzeit.

--Gehoern 12:30, 22. Aug 2005 (CEST)

---

Folgendes ist richtig: Es ist nicht bekannt, ob das Wortproblem in quadratischer Zeit entscheidbar ist. CYK liefert kubisch.

Es gibt aber auch Möglichkeiten auf unter $O(n^{2,5})$ zu kommen!

Gruß --Gerhard Buntrock 02:59, 23. Aug 2005 (CEST)

Platzbedarf

Platzbedarf bei Typ2 Grammatiken soll logarithmus zum quadrat sein? CYK benötigt doch O(n zum quadrat).

Genau das bezweifel ich auch. CYK benötigt auf jeden Fall O(n^2) Platz das er ja eine Tabelle aus n*n, mit n länge des Wortes aufbaut. Terranic 12:34, 11. Okt. 2006 (CEST)

entscheidbar, semi-entscheidbar und berechenbar

Das Wortproblem einer Sprache L ist entscheidbar, wenn ihre charakteristische Funktion χL berechenbar ist.

Die (intuitiv) berechenbaren Funktionen sind gerade die von einer universellen Turingmaschine berechenbaren. Turingmaschinen können genau die Typ-0-Sprachen akzeptieren. Das Halteproblem von Turingmaschinen ist nicht entscheidbar, aber semi-entscheidbar. Das heißt, es gibt Sprachen, deren Wortproblem nur semi-entscheidbar ist, ihre charakteristische Funktion aber berechenbar.

Das Wortproblem für Typ-0-Sprachen ist rekursiv aufzählbar und nicht entscheidbar.

Hiermit könnte das in Einklang gebracht und präzisiert werden. 78.42.66.27 17:00, 3. Jul. 2009 (CEST)