Direkt zum Inhalt

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|ϕnC} 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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Artikel zum Thema

Partnervideos