Satz von Rice

Keine nichttriviale (extensionale) Eigenschaft berechenbarer Funktionen ist entscheidbar. (Satz von Rice)

Beim Satz von Rice handelt es sich um ein Ergebnis der Theoretischen Informatik. Er besagt, dass es unmöglich ist, irgendeinen Aspekt des funktionalen Verhaltens einer Turingmaschine (oder eines Algorithmus in einem anderen Algorithmenmodell) algorithmisch zu überprüfen.

Es ist zwar möglich, eine Eigenschaft eines speziellen Algorithmus zu beweisen, und dies lässt sich auch automatisieren, doch es gibt kein allgemeines Verfahren, das für jeden Algorithmus feststellen kann, ob die von ihm berechnete Funktion eine gewünschte Eigenschaft hat.

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 Codierung, 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 }

unentscheidbar.

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 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 Halteproblem gelangen. Da dies nicht möglich ist, kann C(S) nicht entscheidbar sein.