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.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.