Lexikon der Mathematik: Rice, Satz von
besagt intuitiv, daß es unmöglich ist, einem Algorithmus irgendeine nicht-triviale Eigenschaft der Funktion, die er berechnet, „anzusehen“ (Entscheidbarkeit).
Genauer lautet der Satz von Rice:
Seiϕ1, ϕ2,…eine Aufzählung der berechenbaren Funktionen (welche man durch Arithmeti-sierung aller Turing-Maschinen erhalten kann). Sei C eine beliebige Teilmenge der berechenbaren Funktionen (mit Ausnahme der leeren Menge und der Menge aller berechenbaren Funktionen). Dann ist die Menge {n|ϕn ∈ C} unentscheidbar.
Ein Beispiel: Es ist unentscheidbar festzustellen, ob eine gegebene Turing-Maschine eine konstante Funktion berechnet.
Viele unentscheidbare Probleme, wie das Halteproblem oder das Verifikationsproblem, ergeben sich als Spezialfälle des Satzes von Rice.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.