[ Inhalt ] [ Index ]

Entscheidbare Mengen

Definition: (entscheidbare Menge [9])
Es seinen .
heißt entscheidbar   relativ zu , wenn es einen Algorithmus gibt, mit dessen Hilfe man für jedes Element aus feststellen kann, ob es zu gehört oder nicht:

.

Es sei .
M heißt absolut entscheidbar   oder entscheidbar  , wenn M relativ zu entscheidbar ist.

Entscheidbarkeit ist also eine Eigenschaft einer Menge, nicht eines einzelnen Objekts. Man spricht auch von entscheidbaren Problemen:

''Es ist entscheidbar, ob die Sprache einer beliebigen regulären Grammatik endlich ist.'' (Wie ging das noch??)

Die Menge der Primzahlen ist entscheidbar.

Es ist für eine beliebige Typ-0-Grammatik   G nicht entscheidbar, ob ein gegebenes Wort gilt oder nicht.