Satz von Rice

Der Satz von Rice ist ein Ergebnis der Theoretischen Informatik. Benannt wurde der Satz nach Henry Gordon Rice, der ihn 1953 veröffentlichte. Er besagt, dass es unmöglich ist, irgendeinen nichttrivialen Aspekt des funktionalen Verhaltens einer Turingmaschine (oder eines Algorithmus in einem anderen Algorithmenmodell) algorithmisch zu entscheiden.

Es ist zwar teilweise möglich, eine Eigenschaft eines speziellen Algorithmus zu beweisen, und dies lässt sich auch automatisieren, doch lässt sich aufgrund des gödelschen Unvollständigkeitssatzes nicht jede wahre Aussage über einen gegebenen Algorithmus beweisen. Daher gibt es kein allgemeines Verfahren, das für jeden Algorithmus feststellen kann, ob die von ihm beschriebene Funktion eine gewünschte Eigenschaft hat. Der Satz von Rice zeigt, dass es ein solches Entscheidungsverfahren sogar für keine nichttriviale Eigenschaft gibt.

Formale Fassung

Es sei R die Klasse aller Turing-berechenbaren Funktionen und S eine beliebige nichttriviale (das bedeutet S ≠ ø und S ≠ R) Teilmenge davon. Außerdem ist eine Kodierung, die einem Codewort w die dadurch codierte Turingmaschine M_w zuordnet, vorausgesetzt. Dann ist die Sprache

C(S) = { w | die von M_w berechnete Funktion liegt in S }

nicht entscheidbar.

Aus "die von M_w berechnete Funktion liegt in S" folgt, dass äquivalente Turingmaschinen entweder beide in C(S) liegen oder keine von beiden. Man sagt auch, dass S eine semantische Eigenschaft von Turingmaschinen ist.

Beispiele

Aus dem Satz von Rice folgt beispielsweise, dass es keinen Algorithmus gibt, der für jede Turingmaschine entscheidet, ob sie für jede Eingabe hält. S ist hierbei die Menge aller totalen (überall definierten) Funktionen.

Ebenso ist es nicht entscheidbar, ob eine Turingmaschine eine vorgegebene Funktion berechnet. S enthält dann nur diese eine Funktion. Daraus folgt, dass erst recht das Problem der Programmäquivalenz nicht entscheidbar ist.

Auch lässt es sich nicht entscheiden, ob die berechnete Funktion etwa injektiv, surjektiv oder monoton ist.

Beweisidee

Der Beweis arbeitet mit einer Reduktion des speziellen Halteproblems auf C(S) für ein beliebiges nicht triviales S. Er wird hier durch Pseudocode skizziert.

Es sei S eine nichttriviale Teilmenge von R. Da der Übergang zum Komplement keinen Unterschied für die Entscheidbarkeit macht, kann man ohne Beschränkung der Allgemeinheit annehmen, dass die überall undefinierte Funktion $\bot$ nicht in S enthalten ist. Sei f eine beliebige Funktion aus S. (An dieser Stelle geht ein, dass S nicht trivial ist.) Ferner werde f durch die Turingmaschine M_f berechnet.

Nun betrachtet man für einen beliebigen Algorithmus M_w den folgenden Algorithmus:

function N_w(x):

simuliere M_w mit Eingabe w

simuliere M_f mit Eingabe x und gib das Ergebnis aus

Er hat folgende Eigenschaften:

• Der Übergang von M_w zu N_w ist berechenbar. Es gibt also eine berechenbare Funktion g, so dass M_g(w) = N_w für alle w gilt.
• Falls M_w bei Eingabe von w terminiert, berechnet N_w dieselbe Funktion wie M_f, also f. Andernfalls berechnet N_w die überall undefinierte Funktion $\bot$. Aufgrund der getroffenen Annahmen bedeutet das, dass die von N_w berechnete Funktion genau dann in S liegt, wenn M_w bei Eingabe von w terminiert.

Wenn es nun einen Algorithmus für die Sprache C(S) gäbe, so würde man durch Davorschalten eines Algorithmus für g zu einem Algorithmus zur Lösung des speziellen Halteproblems gelangen. Da dies nicht möglich ist, kann C(S) nicht entscheidbar sein.

Analogon für rekursiv aufzählbare Eigenschaften

Auf eine analoge Weise lassen sich die rekursiv aufzählbaren semantischen Eigenschaften von Turing-Maschinen charakterisieren. Sei S eine Menge rekursiv aufzählbarer Mengen. Dann ist die Sprache

C(S) = { w | die von M_w erkannte Menge liegt in S }

genau dann rekursiv aufzählbar, wenn es eine rekursiv aufzählbare Menge $\mathcal{D}$ von Gödelnummern endlicher Mengen mit folgender Eigenschaft gibt: S enthält genau die rekursiv aufzählbaren Mengen, die eine endliche Teilmenge D haben, deren Gödelnummer #D in $\mathcal{D}$ liegt:

$A \in S \leftrightarrow (A \text{ rekursiv aufzaehlbar} \wedge \exists D (\#D \in \mathcal{D} \wedge D \subseteq A))$

Dass eine solche Menge S rekursiv aufzählbar ist, ist leicht einzusehen. Man startet dazu nacheinander die Berechnungen aller Turingmaschinen und gleichzeitig eine Aufzählung von $\mathcal{D}$. Immer wenn es eine Turingmaschine M_w gibt, die bereits alle Elemente einer schon aufgezählten endlichen Menge D ausgegeben hat, gibt man w aus. Dass alle anderen Mengen nicht rekursiv aufzählbar sein können, lässt sich ähnlich dem Satz von Rice durch die Unlösbarkeit des Halteproblems zeigen.

Siehe auch

• Gödelscher Unvollständigkeitssatz

Literatur

• Hartley Rogers: Theory of recursive functions and effective computability. McGraw-Hill, 1967.